Pagini recente » Cod sursa (job #663768) | Cod sursa (job #3147763) | Cod sursa (job #726326) | Cod sursa (job #2547670) | Cod sursa (job #2736561)
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int prefix[2000005];
vector <int> ans;
int main()
{
string A, B;
fin >> A >> B;
A = " " + A;
B = " " + B;
int j = 0;
for(int i = 1; i < A.size(); i++)
{
while(A[i] != A[j + 1] && j != 0)
j = prefix[j];
if(A[i] == A[j + 1])
j++;
prefix[i] = j;
}
j = 1;
for(int i = 1; i < B.size(); i++)
{
while(B[i] != A[j] && j != 1)
j = prefix[j - 1];
if(B[i] == A[j])
j++;
if(j == A.size())
{
ans.push_back(i - A.size() + 1);
j = prefix[j - 1];
}
}
fout << ans.size() << '\n';
for(int i = 0; i < min(1000, (int)ans.size()); i++)
fout << ans[i] << ' ';
return 0;
}