Pagini recente » Cod sursa (job #220705) | Cod sursa (job #2407882) | Cod sursa (job #3211235) | Cod sursa (job #1922279) | Cod sursa (job #2063226)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("kmp.in");
ofstream fout("kmp.out");
const int NMax = 2000005;
const int maxi = 1000;
char s[NMax], s1[NMax];
int prefixe[NMax];
void Prefix()
{
int i=1, j=0;
prefixe[0] = 0;
int n = strlen(s);
while(i < n)
{
while(j > 0 && s[j] != s[i])
j = prefixe[j-1];
if(s[j] == s[i])
++j;
prefixe[i] = j;
++i;
}
}
void KMP()
{
int n = strlen(s);
int m = strlen(s1);
int j = 0;
int potriviri = 0;
int potriv[maxi+5];
for(int i=0; i<m; ++i)
{
while(j > 0 && s[j]!=s1[i])
j = prefixe[j-1];
if(s[j] == s1[i])
++j;
if(j == n)
{
++potriviri;
if(potriviri <= maxi)
potriv[potriviri] = i - n + 1;
}
}
fout << potriviri << "\n";
for(int i=1; i<=min(maxi,potriviri); ++i)
fout << potriv[i] << " ";
}
int main()
{
fin >> s;
fin >> s1;
Prefix();
KMP();
return 0;
}