fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. // #pragma GCC optimize("Ofast")
  3. // #pragma GCC target("avx,avx2,fma")
  4. // #pragma GCC optimization("unroll-loops")
  5. // #pragma GCC optimize("unroll-loops")
  6. // #pragma GCC optimize("fast-math")
  7. // #pragma GCC optimize("no-stack-protector")
  8. // #define ll __int128
  9. #define ll long long
  10. // #define ll int
  11. #define f(i,a,b) for(int i=a;i<b;i++)
  12. #define mod 1000000007
  13. // #define mod 998244353 
  14. #define mp make_pair
  15. #define uniq(v) (v).erase(unique(all(v)),(v).end())
  16. #define ff first
  17. #define ss second
  18. #define rf(i,a,b) for(int i=a;i>=b;i--)
  19. #define sc(a) scanf("%lld",&a)
  20. #define pf printf
  21. #define sz(a) (int)(a.size())
  22. #define psf push_front
  23. #define ppf pop_front
  24. #define ppb pop_back
  25. #define pb push_back
  26. #define pq priority_queue
  27. #define all(s) s.begin(),s.end()
  28. #define sp(a) setprecision(a)
  29. #define rz resize
  30. #define ld long double
  31. #define inf (ll)1e18
  32. #define ub upper_bound
  33. #define lb lower_bound
  34. #define bs binary_search
  35. #define eb emplace_back
  36. const double pi = acos(-1);
  37. ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
  38. // ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
  39.  
  40. using namespace std;
  41.  
  42. string s1,s2,x;
  43. vector<ll> pre1,pre2,pre3,a;
  44. vector<vector<ll> > prv;
  45.  
  46. void getZarr(string &s, vector<ll> &pre)
  47. {
  48.     int n = s.length();
  49.     int l=0, r=0, k;
  50.  
  51.     // [L,R] make a window which matches with prefix of s
  52.     for(int i=1;i<n;i++)
  53.     {
  54.         //case 1 : within z box
  55.         if(i<r)
  56.         {
  57.             int id=i-l;
  58.             if(pre[id]+i<r)
  59.                 pre[i]=pre[id];
  60.             else
  61.             {
  62.                 l=i,id=r;
  63.                 while(r<n && s[r-l]==s[id])
  64.                     r++,id++;
  65.                 pre[i]=r-l;
  66.             }
  67.         }
  68.         //case 2 : new z box to start
  69.         else
  70.         {  
  71.             int id=i; 
  72.             l=r=i;
  73.             while(r<n && s[r-l]==s[id])
  74.                 r++,id++;
  75.             pre[i]=r-l;
  76.         }
  77.     }
  78. }
  79.  
  80. vector<ll> prefix_function(string &s) {
  81.     int n = (int)s.length();
  82.     vector<ll> pi(n);
  83.     for (int i = 1; i < n; i++) 
  84.     {
  85.         int j = pi[i-1];
  86.         while (j > 0 && s[i] != s[j])
  87.             j = pi[j-1];
  88.         if (s[i] == s[j])
  89.             j++;
  90.         pi[i] = j;
  91.     }
  92.     return pi;
  93. }
  94.  
  95. int main()
  96. {
  97.     ios_base::sync_with_stdio(false);
  98.     cin.tie(NULL);
  99.     // freopen("xortransform.in","r",stdin);
  100.     // freopen("xortransform.out","w",stdout);
  101. // #ifndef ONLINE_JUDGE
  102. //     freopen("input.txt","r",stdin);
  103. //     freopen("output.txt","w",stdout);
  104. // #endif
  105.     int z=1;
  106.     cin>>z;
  107.     f(i,1,z+1)
  108.     {
  109.         //cout<<"Case #"<<i<<": ";
  110.         pre1.clear(),pre2.clear(),a.clear(),pre3.clear(),prv.clear();
  111.         cin>>s1>>s2>>x;
  112.         string temp=s2+"#"+x;
  113.         pre2.rz(sz(temp)+5);
  114.         getZarr(temp,pre2);
  115.         a.rz(sz(x)+2);
  116.         f(i,1,sz(a)-1)
  117.             a[i]=pre2[i+sz(s2)];
  118.         int n=sz(x);
  119.         temp=s1+"#"+x;
  120.         pre1=prefix_function(temp),prv.rz(sz(s1)+5);
  121.         temp=s1;
  122.         pre3=prefix_function(temp);
  123.         vector<ll> mx(sz(s1)+5,-1);
  124.         f(i,1,sz(pre3))
  125.             prv[pre3[i]].pb(i+1LL);
  126.         f(i,1,n+1)
  127.         {
  128.             int len=pre1[i+sz(s1)];
  129.             mx[len]=max(mx[len],pre2[i+1+sz(s2)]),mx[0]=max(mx[0],pre2[i+sz(s2)]);
  130.         }
  131.         rf(i,sz(s1)-1,0)
  132.         {   
  133.             f(j,0,sz(prv[i]))
  134.                 mx[i]=max(mx[(prv[i][j]<=sz(s1))?prv[i][j]:i],mx[i]);
  135.         }
  136.         ll ans=0;
  137.         f(i,0,sz(s1)+1)
  138.             ans+=(1+mx[i]);
  139.         cout<<ans<<"\n";
  140.     }
  141. }
Success #stdin #stdout 0s 5656KB
comments (?)
stdin
copy 
3
ab
bc
abc
aa
bb
ab
aab
acb
bcaabacbc
stdout
copy 
7
4
11
https://ideone.com/Ble4xK
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!