Pagini recente » Cod sursa (job #2021702) | Cod sursa (job #1066533) | Cod sursa (job #2138429) | Cod sursa (job #1153137) | Cod sursa (job #2287914)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000005], B[2000005], pi[2000005];
int n, m, k;
vector <int> v;
int main()
{
fin >> A+1;
fin >> B+1;
n = strlen(A+1);
m = strlen(B+1);
k = 0;
for(int i = 2; i <= n; i++)
{
while(k>0 && A[i] != A[k+1])
k = pi[i];
if(A[k+1] == A[i])
k++;
pi[i] = k;
}
k = 0;
for(int i = 1; i <= m; i++)
{
while(k>0 && A[k+1] != B[i])
k = pi[i];
if(A[k+1] == B[i])
k++;
if(k == n)
{
k = pi[n];
if(v.size() < 1000)
v.push_back(i-n);
}
}
fout << v.size()<<'\n';
for(int i = 0; i < v.size() && i < 1000; i++)
fout << v[i] << " ";
return 0;
}