Pagini recente » Cod sursa (job #2802080) | Cod sursa (job #529302) | Cod sursa (job #2234737) | Cod sursa (job #2171097) | Cod sursa (job #3238482)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int dim=2000001, mod=1e9+7;
int main()
{
int n, m, i, nr1=0, nr2=0, putere[dim], sol[1001], k=0;
char a[dim], b[dim];
f>> a >> b;
n=strlen(a); m=strlen(b);
putere[0]=1;
nr1=(a[0]-'0'); nr2=(b[0]-'0');
for(i=1; i<n; i++){
nr1=(nr1*127LL+(a[i]-'0'))%mod;
nr2=(nr2*127LL+(b[i]-'0'))%mod;
putere[i]=(putere[i-1]*127LL)%mod;
}
putere[n]=(putere[n-1]*127LL)%mod;
if(nr1==nr2){
sol[++k]=0;
}
for(i=n; i<m; i++){
nr2=((nr2*127LL+(b[i]-'0'))-(1LL*(b[i-n]-'0')*putere[n]%mod)+mod)%mod;
if(nr1==nr2){
k++;
if(k<=1000){
sol[k]=i-n+1;
}
}
}
g<< k << endl;
k=min(k, 1000);
for(i=1; i<=k; i++){
g<< sol[i] << " ";
}
return 0;
}