Pagini recente » Cod sursa (job #722160) | Cod sursa (job #1965308) | Cod sursa (job #2423441) | Cod sursa (job #1833000) | Cod sursa (job #344365)
Cod sursa(job #344365)
#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;
fstream f("strmatch.in", ios::in);
fstream g("strmatch.out", ios::out);
void KMP()
{
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;
}
if (nr_sol!=0)
{
if (nr_sol<1000)
{
g<<nr_sol<<"\n";
for (int i=1; i<=nr_sol; ++i)
g<<sol[i]<<" ";
}
else
{
g<<"1000";
for (int i=1; i<=1000; ++i)
g<<sol[i]<<" ";
}
}
else
g<<nr_sol;
f.close();
g.close();
}
int main()
{
KMP();
return 0;
}