Pagini recente » Cod sursa (job #2020851) | Cod sursa (job #26324) | Cod sursa (job #92382) | Cod sursa (job #1924375) | Cod sursa (job #1830894)
#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);
cin >> W+1; n = strlen(W+1);
cin >> S+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++)
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;
}