Pagini recente » Cod sursa (job #1740033) | Cod sursa (job #1903432) | Cod sursa (job #177268) | Cod sursa (job #99746) | Cod sursa (job #288321)
Cod sursa(job #288321)
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#define MAX_L 2000002
using namespace std;
int N, M, Pi[MAX_L];
string A, B;
vector <int> Sol;
void Prefix()
{
int k = 0, i;
Pi[1] = 0;
for ( i = 1; i < N; ++i )
{
while(k > 0 && A[k] != A[i])
k = Pi[k];
if(A[k] == A[i])
++ k;
Pi[i+1] = k;
}
}
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
cin >> A >> B;
N = A.length();
M = B.length();
Prefix();
int q = 0, count = 0, i;
for ( i = 0; i < M; ++i )
{
while(q > 0 && A[q] != B[i])
q = Pi[q];
if(B[i] == A[q])
++ q;
if(q == N && Sol.size() <= 1000)
{
Sol.push_back(i-N+1);
q = Pi[q];
}
}
cout << Sol.size() << "\n";
for ( i = 0; i < Sol.size(); ++i )
cout << Sol[i] << " ";
fclose(stdin);
fclose(stdout);
return 0;
}