Pagini recente » Cod sursa (job #3134411) | Cod sursa (job #1395214) | Cod sursa (job #1513310) | Cod sursa (job #776170) | Cod sursa (job #552378)
Cod sursa(job #552378)
//kmp
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char p[2000000], t[2000000];
int a[2000000], b[2000000], n, m, k=0;
void citire()
{
fin.getline (p, 2000000);
fin.getline (t, 2000000);
m=strlen(p);
n=strlen(t);
}
void kmp1()
{
int i=0, j=-1;
b[i]=j;
while (i<m)
{
while (j>=0 && p[i]!=p[j])
j=b[j];
i++;
j++;
b[i]=j;
}
}
void kmp2()
{
int i=0, j=0;
while (i<n)
{
while (j>=0 && t[i]!=p[j])
j=b[j];
i++;
j++;
if (j==m)
{
k++;
a[k]=(i-j);
j=b[j];
}
}
}
void afisare()
{
fout<<k<<endl;
for(int i=1; i<=k && i<=1000; i++)
fout<<a[i]<<" ";
}
int main()
{
citire();
kmp1();
kmp2();
afisare();
return 0;
}