Pagini recente » Cod sursa (job #433310) | Cod sursa (job #423993) | Cod sursa (job #673621) | Cod sursa (job #434231) | Cod sursa (job #434233)
Cod sursa(job #434233)
#include <fstream>
#include <iostream>
#include <assert.h>
using namespace std;
const int NMAX = 2000005;
void fail_func(char w[], int T[])
{
T[0] = -1;
int i = 1, j = 0, m = 0;
for(; w[i]; ++i) {
if (w[i] == w[j])
T[i] = T[j++];
else {
T[i] = j;
if (w[i] != w[0]) j = 0;
}
if (w[i] == w[m])
++m;
else if (w[i] == w[m = 0] && w[i + 1])
m = 1;
}
T[i] = m;
}
int kmp(char S[], char W[], int T[], int& i)
{
static int j = 0;
for (; S[i]; ) {
if (S[i] == W[j]) {
++i, ++j;
if (!W[j]) {
int x = i - j;
j = T[j];
//assert(j);
//if (j == 0) ++i;
return x;
}
}
else if (T[j] == -1)
++i, j = 0;
else
j = T[j];
}
return -1;
}
char S[NMAX] = {}, W[NMAX] = {};
int main()
{
int *t, i = 0;
int ans[1002] = {}, k = 0, x;
ifstream f1("strmatch.in");
freopen("strmatch.out", "w", stdout);
f1 >> W >> S;
fail_func(W, t = new int [NMAX]);
while( (x = kmp(S, W, t, i)) != -1)
if (k++ <= 1000)
ans[k - 1] = x;
printf("%d\n", k);
for (i = 0; i != k && i != 1000; ++i)
printf("%d ", ans[i]);
printf("\n");
return 0;
}