Pagini recente » Cod sursa (job #2143347) | Cod sursa (job #1698261) | Cod sursa (job #1337738) | Cod sursa (job #3292666) | Cod sursa (job #1804005)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000001],t[2000001];
int urm[2000001],n,m,a[1001];
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;
}
/*for (q=1;q<=m;q++)
cout<<urm[q]<<' ';
cout<<'\n';*/
}
void kmp()
{
int q,k=0,nr=0;
for (q=0;q<n && nr<=1000;q++) {
while (k>0 && p[k]!=t[q])
k=urm[k];
if (p[k]==t[q])
k++;
if (k==m) {
//g<<q-m+1<<' ';
a[++nr]=q-m+1;
}
//cout<<k<<' ';
}
g<<nr<<'\n';
for (q=1;q<=nr;q++)
g<<a[q]<<' ';
}
int main()
{
f.getline(p,2000001);
f.getline(t,2000001);
n=strlen(t);
m=strlen(p);
prefix();
kmp();
return 0;
}