Pagini recente » Cod sursa (job #2268707) | Cod sursa (job #2928765) | Cod sursa (job #2491104) | Cod sursa (job #2872604) | Cod sursa (job #1830900)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define nmax 2000000+5
using namespace std;
// we're looking for W in S
char S[nmax], W[nmax];
int m, n;
int prefix[nmax];
vector<int> sol;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", W+1); n = strlen(W+1);
scanf("\n");
scanf("%s", W+1); m = strlen(S+1);
int i, j;
// form prefix table
j = 0;
prefix[0] = 0;
for (i = 2; i <= n; i++)
{
while (j > 0 && W[j+1] != W[i])
j = prefix[j];
if (W[i] == W[j+1])
j++;
prefix[i] = j;
}
j = 0;
for (i = 1; i <= m; i++)
{
while (S[i] != W[j+1] && j > 0)
j = prefix[j];
if (S[i] == W[j+1])
j++;
if (j == n)
sol.push_back(i-n+1);
}
cout << sol.size() << "\n";
for (i = 0; i < sol.size() && i < 1000; i++)
cout << sol[i]-1 << " ";
//for (i = 1; i <= n; i++)
// cout << W[i] << '\t';
//cout << '\n';
//for (i = 1; i <= n; i++)
// cout << prefix[i] << '\t';
return 0;
}