Pagini recente » Cod sursa (job #622665) | Cod sursa (job #2414130) | Cod sursa (job #2831799) | Cod sursa (job #2730655) | Cod sursa (job #2634815)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2e6 + 5;
int pi[Nmax], ans[Nmax];
int N;
string S, C;
void preproc()
{
int K = 0;
pi[1] = 0;
for(int i = 1; i < C.size(); ++i)
{
while(K > 0 && C[K] != C[i])
K = pi[K];
if(C[K] == C[i])
K++;
pi[i] = K;
//out << pi[i] << " ";
}
}
void solve()
{
int K = 0, L = C.size();
for(int i = 0; i < L; ++i)
{
while(K > 0 && S[K] != C[i])
K = pi[K];
if(S[K] == C[i])
K++;
if(K == S.size())
{
if(N <= 1000)
ans[N++] = (i = i - K + 1);
i++;
}
}
out << N << '\n';
for(int i = 0 ; i < N; ++i)
out << ans[i] << " ";
}
int main()
{
in >> S >> C;
preproc();
solve();
return 0;
}