Pagini recente » Cod sursa (job #647267) | Cod sursa (job #871970) | Cod sursa (job #25910) | Cod sursa (job #1312209) | Cod sursa (job #344368)
Cod sursa(job #344368)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define NMAX 2000010
char a[NMAX];
char b[NMAX];
int next[NMAX];
int sol[1020];
int nr_sol;
void KMP()
{
fstream f("strmatch.in", ios::in);
fstream g("strmatch.out", ios::out);
f>>a;
f>>b;
int n=strlen(a);
int m=strlen(b);
for (int i=n; i>=0; --i)
a[i+1]=a[i];
for (int i=m; i>=0; --i)
b[i+1]=b[i];
int k=0;
int i;
next[1]=0;
for (i=2; i<=n ;++i)
{
while ( k>0 && a[k+1]!=a[i] ) k=next[k];
if (a[k+1]==a[i]) ++k;
next[i]=k;
}
k=0;
for (i=1; i<=m; ++i)
{
while ( k>0 && a[k+1]!=b[i] ) k=next[k];
if (a[k+1]==b[i]) ++k;
if (k==n)
if ( nr_sol<1000 )
sol[++nr_sol]=i-k;
else ++nr_sol;
}
g<<nr_sol;
if (nr_sol>1000)
for (i=1; i<=1000; ++i)
g<<sol[i]<<" ";
else
for (i=1; i<=nr_sol; ++i)
g<<sol[i]<<" ";
f.close();
g.close();
}
int main()
{
KMP();
return 0;
}