Pagini recente » Cod sursa (job #1767818) | Cod sursa (job #1186161) | Cod sursa (job #827997) | Cod sursa (job #2936966) | Cod sursa (job #2911841)
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char p[Nmax], s[Nmax];
int pi[Nmax];
int main()
{
fin >> p;
fin >> s;
///prefix function
int n = strlen(p);
for (int i = 1; i < n; i++)
{
int k = pi[i - 1];
while (k > 0 && p[k] != p[i])
k = pi[k - 1];
if (p[k] == p[i])
k++;
pi[i] = k;
}
///matching
int k = 0, m = strlen(s);
vector <int> sol;
for (int j = 0; j < m; j++)
{
while (k > 0 && p[k] != s[j])
k = pi[k - 1];
if (s[j] == p[k])
k++;
if (k == n)
sol.push_back(j - n + 1);
}
fout << sol.size() << '\n';
if (sol.size() > 1000) sol.resize(1000);
for (auto it : sol)
fout << it << ' ';
return 0;
}