Pagini recente » Cod sursa (job #2469573) | Cod sursa (job #1265275) | Cod sursa (job #1379913) | Cod sursa (job #2705487) | Cod sursa (job #2736574)
#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 = 1;
prefix[1] = 1;
for(int i = 2; i < A.size(); i++)
{
while(A[i] != A[j] && j != 1)
j = prefix[j - 1];
if(A[i] == A[j])
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;
}