Pagini recente » Cod sursa (job #1736771) | Cod sursa (job #457564) | Cod sursa (job #1225076) | Cod sursa (job #935946) | Cod sursa (job #1808223)
#include <iostream>
#include <fstream>
#include <string.h>
#define pmax 2000099
using namespace std;
char p[pmax],s[pmax];
int sol[pmax],nr,urm[pmax];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{int k,m,n,i;
fin.getline(p,pmax);
m=strlen(p);
urm[0]=-1;k=-1;
for(i=1;i<m;i++)
{ while(k>=0 && p[k+1]!=p[i])k=urm[k];
if(p[k+1]==p[i])k++;
urm[i]=k;
}
k=-1;
fin.getline(s,pmax);
n=strlen(s);
for(i=0;i<n;i++)
{ while(k>0 && p[k+1]!=s[i])k=urm[k];
if(p[k+1]==s[i])k++;
if(k==m-1)
{sol[++nr]=i-m+1;
k=urm[k];
}
}
fout<<nr<<'\n';
for(i=1;i<=nr;i++)fout<<sol[i]<<'\n';
}