Pagini recente » Cod sursa (job #1189491) | Cod sursa (job #397119) | Cod sursa (job #2046935) | Cod sursa (job #2320049) | Cod sursa (job #2233791)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int LONG=2000000;
const int MOD=666013;
const int P=73;
char pattern[LONG+1];
char text[LONG+1];
int sol[LONG+1];
int main()
{
fin.getline(pattern, LONG+1);
fin.getline(text, LONG+1);
int N=strlen(text);
int M=strlen(pattern);
if(M>N)
{
fout<<"0\n";
return 0;
}
int aux=1, pat=0, txt=0;
for(int i=0; i<M-1; ++i)
aux=(aux*P)%MOD;
for(int i=0; i<M; ++i)
{
pat=(P*pat+pattern[i])%MOD;
txt=(P*txt+text[i])%MOD;
}
int k=0;
for(int i=0; i<=N-M; ++i)
{
if(pat==txt)
{
bool ok=1;
for(int j=0; j<M && ok; ++j)
if(text[i+j]!=pattern[j]) ok=0;
if(ok) sol[++k]=i;
}
if(i<N-M)
{
txt=(P*(txt-text[i]*aux)+text[i+M])%MOD;
if(text<0) txt=txt+MOD;
}
}
fout<<k<<"\n";
for(int i=1; i<=k && i<=1000; ++i) fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}