Pagini recente » Cod sursa (job #1210790) | Cod sursa (job #633453) | Cod sursa (job #2866436) | Cod sursa (job #501) | Cod sursa (job #1368611)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char P[2000010],T[2000010];
int urm[2000010],v[1001];
int main()
{
int k=-1,i,nr=0;
fin.getline(P,2000100);
fin.getline(T,2000100);
int n=strlen(P);
int m=strlen(T);
urm[0]=0;
for(i=1;i<n;i++)
{
while(k>0&&P[k+1]!=P[i]) k=urm[k];
if(P[k+1]==P[i]) k++;
urm[i]=k;
}
k=-1;
for(i=0;i<m;i++)
{
while(k>0&&P[k+1]!=T[i]) k=urm[k];
if(P[k+1]==T[i]) k++;
if(k==n-1)
{
nr++;
v[nr]=i-n+1;
k=urm[k];
}
}
fout<<nr<<"\n";
for(i=1;i<=nr&&i<=1000;i++) fout<<v[i]<<" ";
}