Pagini recente » Cod sursa (job #2546763) | Cod sursa (job #2889327) | Cod sursa (job #2330436) | Cod sursa (job #2620828) | Cod sursa (job #786214)
Cod sursa(job #786214)
// KMP_wikipedia.cpp :
//#include "stdafx.h"
#include <fstream>
#define NMAX 2000005
using namespace std;
ifstream f ("strmatch.in"); ofstream g ("strmatch.out");
char P[NMAX], T[NMAX];
int k=-1, n, m, L[NMAX], s[1000], sk;
long long nr;
void kmp()
{for (int t = 0; t < n; t++) {
while (k > 0 && P[k+1] != T[t]) k = L[k];
if (P[k+1] == T[t]) k++;
if (k == m-1) {
nr++;
if(sk<1000) s[++sk] = t-m+1;
k = L[k];
}
}
}
int main()
{f>>P>>T;
n = strlen(T);
m = strlen(P);
kmp();
g<<nr<<"\n";
for(int i=1;i<=sk;i++) g<<s[i]<<" ";
g<<"\n";
return 0;
}