Pagini recente » Cod sursa (job #1539590) | Cod sursa (job #1308927) | Cod sursa (job #2689972) | Cod sursa (job #2059516) | Cod sursa (job #344555)
Cod sursa(job #344555)
//KMP
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define N 2000009
char a[N];
char b[N];
int next[N];
int nr_sol;
int sol[1010];
int min(int i, int j)
{
if (i > j)
return j;
else
return i;
}
void KMP()
{
fstream f("strmatch.in", ios::in);
fstream g("strmatch.out", ios::out);
f>>a;
f>>b;
int lenght_a=strlen(a);
int lenght_b=strlen(b);
int i,j;
for (i=lenght_a; i>=0; --i)
a[i+1]=a[i];
for (j=lenght_b; j>=0; --j)
b[j+1]=b[j];
int k=0;
next[1]=0;
for (i=2; i<=lenght_a; ++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<=lenght_b; ++i)
{
while (k>0 && a[k+1]!=b[i]) k=next[k];
if (a[k+1]==b[i]) ++k;
if (k==lenght_a)
{
if (nr_sol<1000)
sol[++nr_sol]=i-lenght_a;
else
++nr_sol;
}
}
g<<nr_sol<<"\n";
for (i=1;i<=min(nr_sol,1000);++i)
g<<sol[i]<<" ";
f.close();
g.close();
}
int main()
{
KMP();
return 0;
}