Pagini recente » Cod sursa (job #264067) | Cod sursa (job #731315) | Cod sursa (job #2593111) | Cod sursa (job #2518639) | Cod sursa (job #478102)
Cod sursa(job #478102)
#include<fstream>
#include<string.h>
#define NM 2000001
using namespace std;
char t[2000001],p[2000001];
int u[2000001],n,m,s[1001];
void urm()
{int q,k=-1;
u[0]=-1;
for(q=1;q<m;++q)
{while(k>-1&&p[k+1]!=p[q])
k=u[k];
if(p[k+1]==p[q])
k++;
u[q]=k;}}
int main()
{ifstream in("strmatch.in");
ofstream out("strmatch.out");
in>>p>>t;
int i,k=0,q;
m=strlen(p);
n=strlen(t);
urm();
q=-1;
for(i=0;i<n;++i)
{while(q>-1&&p[q+1]!=t[i])
q=u[q];
if(p[q+1]==t[i])
q++;
if(q==m-1)
{k++;
if(k<=1000)
s[k]=i-m+1;
q=u[q];}}
out<<k<<"\n";
for(i=1;i<=k&&i<=1000;++i)
out<<s[i]<<" ";
return 0;
}