Pagini recente » Cod sursa (job #2593653) | Cod sursa (job #1509077) | Cod sursa (job #1738133) | Cod sursa (job #2742844) | Cod sursa (job #2738894)
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9+7;
const int MOD2 = 1e9+9;
const int MOD3 = 1e9+13;
const int NMAX = 1e6*2;
char s1[NMAX+6] , s2[NMAX + 6];
vector<int>sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1,NMAX*2+5,stdin);
fgets(s2,NMAX*2+5,stdin);
int n = strlen(s1) , m = strlen(s2) , i;
--n ;
--m;
long long cnt1 = 0 , cnt2 = 0 , cnt3 = 0 ;
for(i = 0 ; i < n ;i++)
{
cnt1 = cnt1*97 + s1[i]-'0';
cnt2 = cnt2*97 + s1[i]-'0';
cnt3 = cnt3*97 +s1[i]-'0';
cnt1%=MOD1;
cnt2%=MOD2;
cnt3%=MOD3;
}
long long c1 = 0 , c2 = 0 ,p1 = 1, p2 = 1,p3=1,c3=0;
for(i = 0 ; i < n; i++)
{
c1 = c1*97 + s2[i]-'0';
c2 = c2*97 + s2[i]-'0';
c3 = c3*97 + s2[i]-'0';
c1%=MOD1;
c2%=MOD2;
c3%=MOD3;
if(n - i - 1)
{p1= p1*97;
p1%=MOD1;
p2*=97;
p2%=MOD2;
p3*=97;
p3%=MOD3;}
}
int answer = 0 ;
if(c1 == cnt1 && c2 == cnt2&&c3 == cnt3)answer ++,sol.push_back(n-1);
for(i = n ; i < m; i++)
{
c1 -= p1*(s2[i-n]-'0');
c1 *= 97;
c1 += s2[i]-'0';
c1%=MOD1;
if(c1<0)c1+=MOD1;
c2 -= p2*(s2[i-n]-'0');
c2 *= 97;
c2 += s2[i]-'0';
c2%=MOD2;
if(c2<0)c2+=MOD2;
c3 -= p3*(s2[i-n]-'0');
c3 *= 97;
c3 += s2[i]-'0';
c3%=MOD3;
if(c3<0)c3+=MOD3;
if(c1 == cnt1 && c2 == cnt2&& c3 == cnt3)answer ++,sol.push_back(i);
}
cout << answer<<endl;
for(auto edge : sol)
cout<<edge - n+1<< " ";
return 0;
}