Pagini recente » Cod sursa (job #1330078) | Cod sursa (job #1841881) | Cod sursa (job #360380) | Cod sursa (job #2372222) | Cod sursa (job #3238393)
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int dim=2000001, mod1=pow(10, 9)+7, mod2=pow(10, 9)+9;
int main()
{
int n, m, i, nr1=0, nr2=0, nr3=0, nr4=0, putere[dim], sol[dim], k=0;
char a[dim], b[dim];
f>> a >> b;
n=strlen(a); m=strlen(b);
putere[0]=1;
nr1=a[0]-'A'; nr2=b[0]-'A';
nr3=a[0]-'A'; nr4=b[0]-'A';
for(i=1; i<n; i++){
nr1=(nr1*26LL+a[i]-'A')%mod1; nr2=(nr2*26LL+b[i]-'A')%mod1;
nr3=(nr3*26LL+a[i]-'A')%mod2; nr4=(nr4*26LL+b[i]-'A')%mod2;
putere[i]=(putere[i-1]*26LL)%mod1;
}
putere[n]=(putere[n-1]*26LL)%mod1;
if(nr1==nr2 && nr3==nr4){
sol[++k]=0;
}
for(i=n; i<m; i++){
nr2=((nr2*26LL+b[i]-'A')-(1LL*(b[i-n]-'A')*putere[n]%mod1)+mod1)%mod1;
nr4=((nr4*26LL+b[i]-'A')-(1LL*(b[i-n]-'A')*putere[n]%mod2)+mod2)%mod2;
if(nr1==nr2 && nr3==nr4){
sol[++k]=i-n+1;
if(k==1000){
break;
}
}
}
g<< k << endl;
for(i=1; i<=k; i++){
g<< sol[i] << " ";
}
return 0;
}