Pagini recente » Cod sursa (job #1478830) | Cod sursa (job #2582225) | Cod sursa (job #856719)
Cod sursa(job #856719)
#include<cstdio>
#include<string.h>
#include<fstream>
#define dim 2000001
using namespace std;
int p[1000],poz[dim];
int m,n,x;
char a[dim],b[dim];
void KMP_calcul()
{
int k = 0;
p[1] = 0;
for(int i = 2 ; i<=m; i++)
{
while( (k > 0) && (b[k+1] != b[i]))
k = p[k];
if(b[k+1] == b[i])
k++;
p[i] = k;
}
}
void KMP_potrivire()
{
int q = 0;
for(int i = 1; i<=n ; i++)
{
while((q>0) && (a[i] != b[q+1]))
q = p[q];
if(a[i] == b[q+1])
q++;
if(q==m)
{
if(x<1000)
poz[x] = i - m;
x++;
q = p[q];
}
}
}
int main()
{
ifstream f("grader_test38.in");
ofstream g("strmatch.out");
f >> (b+1) >> (a+1);
n = strlen(a+1);
m = strlen(b+1);
KMP_calcul();
KMP_potrivire();
g << x << "\n";
if(x > 1000)
x = 1000;
for(int i = 0 ; i < x; i++)
g << poz[i] <<" ";
return 0;
}