Pagini recente » Cod sursa (job #1191255) | Cod sursa (job #2056439) | Cod sursa (job #1010325) | Cod sursa (job #1981268) | Cod sursa (job #1803985)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000001],s[2000001];
int m,urm[2000003],nr,v[1005],n,t;
void prefix()
{
int i,k=0;
urm[1]=0;
for(i=2;i<=m;i++)
{
while(k>0&&p[k]!=p[i-1])
k=urm[k];
if(p[k]==p[i-1])k++;
urm[i]=k;
}
}
void kmp()
{
int q,k=0;
for(q=0;q<n;q++)
{
while(k>0&& p[k]!=s[q])
k=urm[k];
if(p[k]==s[q])k++;
if(k==m) {nr++;if(t<=1000)v[++t]=q-m+1;}
}
}
int main()
{
int i;
f.getline(p,256);
f.getline(s,2000);
m=strlen(p);
n=strlen(s);
if(m>n)g<<0;
else {
prefix();
kmp();
g<<nr<<'\n';
if(t>1000) t=1000;
for(i=1;i<=t;i++)
g<<v[i]<<" ";
}
return 0;
}