Pagini recente » Cod sursa (job #1241934) | Cod sursa (job #1312464) | Cod sursa (job #1617924) | Cod sursa (job #1774892) | Cod sursa (job #2734680)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000008], B[2000008];
int pi[2000008], i, cnt, pcnt, M, N;
queue<int> Q;
void kmp()
{
int k = 0;
pi[1] = 0;
for (i = 2; i <= M; i++)
{
while(k>0 && A[k+1] != A[i])
k = pi[k];
if (A[k+1] == A[i])
k++;
pi[i] = k;
}
}
int main()
{
fin >> A >> B;
/*for (; (A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z')
|| (A[M] >= '0' && A[M] <= '9'); ++M);
for (; (B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z')
|| (B[N] >= '0' && B[N] <= '9'); ++N);*/
M = strlen(A);
N = strlen(B);
for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';
for (i = N; i; --i) B[i] = B[i-1]; B[0] = ' ';
kmp();
int q = 0;
for (i = 1; i <= N; i++)
{
while (q > 0 && A[q+1]!= B[i])
q = pi[q];
if (A[q+1] == B[i])
q++;
if (q == M)
{
cnt++;
if (cnt <= 1000)
Q.push(i-M);
}
}
fout << cnt << "\n";
while (! Q.empty())
{
fout << Q.front() << " ";
Q.pop();
}
return 0;
}