Pagini recente » Cod sursa (job #459085) | Cod sursa (job #276799) | Cod sursa (job #609712) | Cod sursa (job #2616059) | Cod sursa (job #434049)
Cod sursa(job #434049)
#include <fstream>
#include <iostream>
using namespace std;
const int NMAX = 2000001;
void fail_func(char w[], int T[])
{
T[0] = -1;
int i = 1, j = 0;
for(; w[i]; ++i)
if (w[i] == w[j])
T[i] = T[j++];
else {
T[i] = j;
j = 0;
}
T[i] = j;
}
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];
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[1001] = {}, k = 0;
ifstream f1("strmatch.in");
freopen("strmatch.out", "w", stdout);
f1 >> W >> S;
fail_func(W, t = new int [NMAX]);
while( (ans[k] = kmp(S, W, t, i)) != -1 && ++k != 1000 );
printf("%d\n", k);
for (i = 0; i != k; ++i)
printf("%d ", ans[i]);
return 0;
}