fork 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 mod 1000000007
  41. #define For(i,n) for(int i=0;i<n;i++)
  42. #define Rep(i,x,y) for(int i=x;i<=y;i++)
  43. #define eps 1e-8
  44. #define ff first
  45. #define ss second
  46. #define mem(a,b) memset(a,b,sizeof(a))
  47. #define min3(a,b,c) min(a,min(b,c))
  48. #define max3(a,b,c) max(a,max(b,c))
  49. #define READ freopen("input.txt", "r", stdin)
  50. #define WRITE freopen("output.txt","w", stdout)
  51. #define sz size()
  52. #define dbg(x) printf("yo is %d!\n",x)
  53. #define dbg2(x,y) printf("yo is %d! and %d!\n",x,y)
  54. #define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
  55. #define sqr(a) (a) * (a)
  56. #define clr clear()
  57. #define CASE(a) printf("Case %d: ",a)
  58. #define sf(n) scanf("%d", &n)
  59. #define sff(a,b) scanf("%d %d", &a, &b)
  60. #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
  61.  
  62. //int dx[] = {0,1,0,-1};
  63. //int dy[] = {1,0,-1,0};
  64. //int dx[] = { -1, -1,  0, 1, 1, 1,  0, -1 };
  65. //int dy[] = {  0, -1, -1, -1,  0, 1, 1, 1 };
  66. //int dxK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
  67. //int dyK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
  68.  
  69. //functions
  70.  
  71. //i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}
  72.  
  73. //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();}}
  74.  
  75. //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');}
  76.  
  77. //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;}
  78.  
  79. //i64 modinverse(i64 num){return bigmod(num,mod-2);}
  80.  
  81. //void combination(int pos,int last){if(pos==k+1){for(int i=1;i<=k;i++)cout << tem[i];cout << endl;return;}
  82. //for(int i=last+1;i<=n-k+pos;i++){tem[pos] = num[i-1];combination(pos+1,i);}}
  83. //i64 power(i64 value, i64 base){i64 result = 1;For(i,base)result *= value;return result;}
  84. //int Set(int N,int pos){return N = (1<<pos);}
  85. //int reset(int N,int pos){return N &= (~(1<<pos));}
  86. //bool check(int N,int pos){return (bool)(N & (1<<pos));}
  87.  
  88. //typedef tree< int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > Set;
  89.  
  90. i64 bigmod(i64 num,i64 n)   // used to calculate num^n
  91. {
  92.     if(n==0)
  93.         return 1;
  94.     i64 x = bigmod(num,n/2);
  95.     x = x*x%mod;
  96.     if(n%2==1)
  97.         x = x*num % mod;
  98.     return x;
  99. }
  100.  
  101. i64 modinverse(i64 num)
  102. {
  103.     return bigmod(num,mod-2) % mod;
  104. }
  105.  
  106. #define MAX 250005
  107. #define p1 281
  108. #define p2 283
  109. #define mod1 1000000007
  110. #define mod2 1000000009
  111.  
  112. i64 pr1[MAX], pr2[MAX];
  113.  
  114. i64 h1, h2, h3, h4;
  115.  
  116. void prime_calc()
  117. {
  118.     pr1[0] = 1;
  119.     pr2[0] = 1;
  120.  
  121.     Rep(i,1,MAX-1)
  122.     {
  123.         pr1[i] = (pr1[i-1] * p1) % mod1;
  124.         pr2[i] = (pr2[i-1] * p2) % mod2;
  125.     }
  126. }
  127.  
  128. int main()
  129. {
  130.     prime_calc();
  131.     int n;
  132.     cin >> n;
  133.  
  134.     string s1, s2;
  135.     cin >> s1 >> s2;
  136.  
  137.     if(s1==s2)
  138.     {
  139.         cout << 0 << endl;
  140.         return 0;
  141.     }
  142.  
  143.     int cnt = 0;
  144. 	// calculating hash values of s1 and s2
  145.     for(int i = s1.sz-1; i>=0; i--)
  146.     {
  147.         h1 += (s1[i]*pr1[cnt])%mod1;
  148.         h1 %= mod1;
  149.         h2 += (s1[i]*pr2[cnt])%mod2;
  150.         h2 %= mod2;
  151.         h3 += (s2[i]*pr1[cnt])%mod1;
  152.         h3 %= mod1;
  153.         h4 += (s2[i]*pr2[cnt])%mod2;
  154.         h4 %= mod2;
  155.         cnt++;
  156.     }
  157.  
  158.     //cout << h1 << " " << h2 << " " << h3 << " " << h4 << endl;
  159.  
  160.     Rep(i,1,n-1)
  161.     {
  162.     	//pulling from last
  163.         h1 = (h1-s1[n-i]+mod1)%mod1;
  164.         h1 = h1*modinverse(p1);
  165.         h1 %= mod1;
  166.     	//pulling from last
  167.         h2 = (h2-s1[n-i]+mod2)%mod2;
  168.         h2 = h2*modinverse(p2);
  169.         h2 %= mod2;
  170.  
  171.         // adding to first
  172.         h1 += (s1[n-i]*pr1[n-1])%mod1;
  173.         h1 %= mod1;
  174.         //adding to first
  175.         h2 += (s1[n-i]*pr2[n-1])%mod2;
  176.         h2 %= mod2;
  177.  
  178.         cout << h1 << " " << h2 << " " << h3 << " " << h4 << endl;
  179.  
  180.         if(h1==h3 && h2==h4)
  181.         {
  182.             cout << i << endl;
  183.             return 0;
  184.         }
  185.     }
  186.  
  187.     cout << -1 << endl;
  188.  
  189.     return 0;
  190. }
  191.  
Success #stdin #stdout 0s 19144KB
comments (?)
stdin
copy 
2
ab
ba
stdout
copy 
27635 999992144 27635 27831
-1
https://ideone.com/2YsOxs
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!