Pagini recente » Cod sursa (job #2492346) | Cod sursa (job #792808) | Cod sursa (job #200442) | Cod sursa (job #3243239) | Cod sursa (job #2717340)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string N, M;
int n, m;
int pi[2000005];
vector<int> sol;
void precalc()
{
int k = -1;
pi[0] = -1;
for (int i=1;i<n;i++)
{
while (k != -1 && N[k+1] != N[i])
k = pi[k];
if (N[k+1] == N[i])
k++;
pi[i] = k;
}
}
void kmp()
{
int q = -1;
for (int i=0;i<m;i++)
{
while (q != -1 && N[q + 1] != M[i])
q = pi[q];
if (N[q + 1] == M[i])
q = q + 1;
if (q == n - 1)
sol.push_back(i - n + 1);
}
}
int main()
{
cin >> N >> M;
n = N.length();
m = M.length();
precalc();
kmp();
cout << sol.size() << '\n';
for (int i : sol)
cout << i << ' ';
return 0;
}