Pagini recente » Cod sursa (job #3219401) | Cod sursa (job #934442) | Cod sursa (job #3241627) | Cod sursa (job #3147149) | Cod sursa (job #1423919)
#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
char S[2000010], T[2000010];
int i, k, N, M, prefix[2000010], sol;
vector<int> solution;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf(" %s",(S+1));
scanf(" %s",(T+1));
N = strlen((S+1));
M = strlen((T+1));
for(i = 2; i <= N; i++)
{
while(k && S[k + 1] != S[i])
k = prefix[k];
if(S[k + 1] == S[i])
k = k + 1;
prefix[i] = k;
}
for(i = 1, k = 0; i <= M; i++)
{
while(k && S[k + 1] != T[i])
k = prefix[k];
if(S[k + 1] == T[i])
k = k + 1;
if(k == N)
{
if(sol < 1000)
solution.push_back(i - N);
sol = sol + 1;
k = prefix[k];
}
}
printf("%d\n",sol);
for(vector<int>::iterator it = solution.begin(); it != solution.end(); it++)
printf("%d ", *it);
return 0;
}