fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3.  
  4. #define gc getchar
  5. #define pc putchar
  6.  
  7. using namespace std;
  8.  
  9. /*#include <ext/pb_ds/tree_policy.hpp>
  10. #include <ext/pb_ds/detail/standard_policies.hpp>
  11. #include <ext/pb_ds/assoc_container.hpp>
  12.  
  13. using namespace __gnu_pbds;
  14. */
  15.  
  16. /*
  17.         two functions for policy based data structure. it is
  18.  
  19.                 find_by_order() and order_of_key().
  20.  
  21.         The first returns an iterator to the k-th largest element (counting from zero),
  22.         the second returns the number of items in a set that are strictly smaller than our item
  23.  
  24. */
  25.  
  26. #define vi vector<int>
  27. #define si set<int>
  28. #define vs vector<string>
  29. #define pii pair<int,int>
  30. #define vpi vector<pii>
  31. #define pri priority_queue<int>
  32. #define rev_pri priority_queue<int,vector<int>,greater<int> >
  33. #define mpi map<int,int>
  34. #define i64 long long int
  35. #define endl '\n'
  36. #define pi acos(-1)
  37. #define all(v) v.begin(),v.end()
  38. #define pb push_back
  39. #define mp make_pair
  40. #define For(i,n) for(int i=0;i<n;i++)
  41. #define Rep(i,x,y) for(int i=x;i<=y;i++)
  42. #define eps 1e-8
  43. #define ff first
  44. #define ss second
  45. #define mem(a,b) memset(a,b,sizeof(a))
  46. #define min3(a,b,c) min(a,min(b,c))
  47. #define max3(a,b,c) max(a,max(b,c))
  48. #define READ freopen("input.txt", "r", stdin)
  49. #define WRITE freopen("output.txt","w", stdout)
  50. #define sz size()
  51. #define dbg(x) printf("yo is %d!\n",x)
  52. #define dbg2(x,y) printf("yo is %d! and %d!\n",x,y)
  53. #define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
  54. #define sqr(a) (a) * (a)
  55. #define clr clear()
  56. #define CASE(a) printf("Case %d: ",a)
  57. #define sf(n) scanf("%d", &n)
  58. #define sff(a,b) scanf("%d %d", &a, &b)
  59. #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
  60.  
  61. //int dx[] = {0,1,0,-1};
  62. //int dy[] = {1,0,-1,0};
  63. //int dx[] = { -1, -1,  0, 1, 1, 1,  0, -1 };
  64. //int dy[] = {  0, -1, -1, -1,  0, 1, 1, 1 };
  65. //int dxK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
  66. //int dyK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
  67.  
  68. //functions
  69.  
  70. //i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}
  71.  
  72. //inline void fastRead(i64 *a){register char c=0;while(c<33)c=gc();*a=0;while(c>33){*a=*a*10+c-'0';c=gc();}}
  73.  
  74. //inline void fastWrite(int a){char snum[20];int i=0;do{snum[i++]=a%10+48;a=a/10;}while(a!=0);i=i-1;while(i>=0)pc(snum[i--]);pc('\n');}
  75.  
  76. //i64 bigmod(i64 num,i64 n){if(!n)return 1;i64 x=(bigmod(num,n/2)*bigmod(num,n/2))%mod;if(n%2)x=(x*num)%mod;return x;}
  77.  
  78. //i64 modinverse(i64 num){return bigmod(num,mod-2);}
  79.  
  80. //void combination(int pos,int last){if(pos==k+1){for(int i=1;i<=k;i++)cout << tem[i];cout << endl;return;}
  81. //for(int i=last+1;i<=n-k+pos;i++){tem[pos] = num[i-1];combination(pos+1,i);}}
  82. //i64 power(i64 value, i64 base){i64 result = 1;For(i,base)result *= value;return result;}
  83. //int Set(int N,int pos){return N = (1<<pos);}
  84. //int reset(int N,int pos){return N &= (~(1<<pos));}
  85. //bool check(int N,int pos){return (bool)(N & (1<<pos));}
  86.  
  87. //typedef tree< int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > Set;
  88.  
  89. #define MAX 250005
  90. #define p1 131
  91. #define p2 999683
  92. #define p3 169
  93. #define mod1 1000000007
  94. #define mod2 1000000009
  95. #define mod3 1000000021
  96.  
  97. i64 mod;
  98.  
  99. i64 bigmod(i64 num,i64 n)   // used to calculate num^n
  100. {
  101.     if(n==0)
  102.         return 1;
  103.     i64 x = bigmod(num,n/2);
  104.     x = x*x%mod;
  105.     if(n%2==1)
  106.         x = x*num % mod;
  107.     return x;
  108. }
  109.  
  110. i64 modinverse(i64 num)
  111. {
  112.     return bigmod(num,mod-2) % mod;
  113. }
  114.  
  115. i64 pr1[MAX], pr2[MAX], pr3[MAX];
  116.  
  117. i64 h1, h2, h3, h4, h5, h6;
  118.  
  119. void prime_calc()
  120. {
  121.     pr1[0] = 1;
  122.     pr2[0] = 1;
  123.     pr3[0] = 1;
  124.  
  125.     Rep(i,1,MAX-1)
  126.     {
  127.         pr1[i] = (pr1[i-1] * p1) % mod1;
  128.         pr2[i] = (pr2[i-1] * p2) % mod2;
  129.         pr3[i] = (pr3[i-1] * p3) % mod3;
  130.     }
  131. }
  132.  
  133. int main()
  134. {
  135.     prime_calc();
  136.     int n;
  137.     cin >> n;
  138.  
  139.     string s1, s2;
  140.     cin >> s1 >> s2;
  141.  
  142.     if(s1==s2)
  143.     {
  144.         cout << 0 << endl;
  145.         return 0;
  146.     }
  147.  
  148.     int cnt = 0;
  149.  
  150.     for(int i = s1.sz-1; i>=0; i--)
  151.     {
  152.         h1 += (s1[i]*pr1[cnt])%mod1;
  153.         h1 %= mod1;
  154.         h2 += (s1[i]*pr2[cnt])%mod2;
  155.         h2 %= mod2;
  156.         h3 += (s1[i]*pr3[cnt])%mod3;
  157.         h3 %= mod3;
  158.         h4 += (s2[i]*pr1[cnt])%mod1;
  159.         h4 %= mod1;
  160.         h5 += (s2[i]*pr2[cnt])%mod2;
  161.         h5 %= mod2;
  162.         h6 += (s2[i]*pr3[cnt])%mod3;
  163.         h6 %= mod3;
  164.         cnt++;
  165.     }
  166.  
  167.     //cout << h1 << " " << h2 << " " << h3 << " " << h4 << " " << h5 << " " << h6 << endl;
  168.  
  169.     Rep(i,1,n-1)
  170.     {
  171.         h1 = (h1-s1[n-i]+mod1)%mod1;
  172.         mod = mod1;
  173.         h1 = h1*modinverse(p1);
  174.         h1 %= mod1;
  175.  
  176.         h2 = (h2-s1[n-i]+mod2)%mod2;
  177.         mod = mod2;
  178.         h2 = h2*modinverse(p2);
  179.         h2 %= mod2;
  180.  
  181.         h3 = (h3-s1[n-i]+mod3)%mod3;
  182.         mod = mod3;
  183.         h3 = h3*modinverse(p3);
  184.         h3 %= mod3;
  185.         //cout << h1 << " " << h2 << " " << h3 << " " << h4 << " " << h5 << " " << h6 << endl;
  186.         h1 += (s1[n-i]*pr1[n-1])%mod1;
  187.         h1 %= mod1;
  188.         h2 += (s1[n-i]*pr2[n-1])%mod2;
  189.         h2 %= mod2;
  190.         h3+= (s1[n-i]*pr3[n-1])%mod3;
  191.         h3 %= mod3;
  192.  
  193.         //cout << h1 << " " << h2 << " " << h3 << " " << h4 << " " << h5 << " " << h6 << endl;
  194.  
  195.         if(h1==h4 && h2==h5 && h3==h6)
  196.         {
  197.             cout << i << endl;
  198.             return 0;
  199.         }
  200.     }
  201.  
  202.     cout << -1 << endl;
  203.  
  204.     return 0;
  205. }
  206.  
Success #stdin #stdout 0s 21104KB
comments (?)
stdin
copy 
11
abracadabra
racadabraab
stdout
copy 
9
https://ideone.com/M9a9w4
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!