Pagini recente » Cod sursa (job #2105859) | Cod sursa (job #376731) | Cod sursa (job #751305) | Cod sursa (job #1020722) | Cod sursa (job #922325)
Cod sursa(job #922325)
#include <fstream>
#include <cstring>
#define NMAX 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,j,n1,n2,rez[NMAX],k,ok,l[NMAX],p,nr;
char s1[NMAX],s2[NMAX];
int main()
{
fin.get(s2,NMAX);
fin.get();
fin.get(s1,NMAX);
n1=strlen(s1);
n2=strlen(s2);
if(n2>n1)
fout<<0<<'\n';
else
{
for(i=0;i<n2;++i)
l[i]=-1;
for(p=1;p<n2;++p)
{
k=l[p-1];
while(k>0&&s2[k+1]!=s2[p])
k=l[k];
if(s2[k+1]==s2[p])
k++;
l[p]=k;
}
k=-1;
for(int t=0;t<n1;++t)
{
while(k>0&&s1[t]!=s2[k+1])
k=l[k];
if(s1[t]==s2[k+1])
k++;
if(k+1==n2)
{rez[++nr]=t-k;k=l[k];
if(nr>=1000)
{
fout<<nr<<'\n';
for(i=1;i<=nr;++i)
fout<<rez[i]<<" ";
return 0;
}
}
}
fout<<nr<<'\n';
for(i=1;i<=nr;++i)
fout<<rez[i]<<" ";
}
return 0;
}