Pagini recente » Cod sursa (job #1876534) | Cod sursa (job #3247411) | Cod sursa (job #2583578) | Cod sursa (job #26907) | Cod sursa (job #1803991)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int urm[2000],m,n,nr,l,u[1001];
char p[2000001],t[2000001];
void citire ()
{
f.get(p,2000001);f.get();
f.get(t,2000001);
m=strlen(p);n=strlen(t);
}
void prefix ()
{
int q,k;
k=0;
urm[1]=0;
for(q=2;q<=m;q++)
{
while(k>0 && p[k]!=p[q-1])
k=urm[k];
if(p[k]==p[q-1])k++;
urm[q]=k;
}
}
void kmp ()
{
int q,k;
k=0;
for(q=0;q<=n;q++)
{
while(k>0 && p[k]!=t[q])
k=urm[k];
if(p[k]==t[q])k++;
if(k==m)
{
if (l<=1000)
{
l++;
u[l]=q-m+1;
}
nr++;
}
}
g<<nr<<'\n';
}
int main()
{
int i;
citire();
prefix();
kmp();
for (i=1;i<=l;i++)
g<<u[i]<<" ";
}