Pagini recente » Cod sursa (job #2627388) | Cod sursa (job #2371911) | Cod sursa (job #3176678) | Cod sursa (job #3144281) | Cod sursa (job #2817378)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6;
int pi[NMAX + 5],ans[1005];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,cnt = 0,k;
string s1,s2;
fin >> s1 >> s2;
n = s1.size();
m = s2.size();
k = -1;
pi[0] = -1;
for (int i = 1;i < n;i++) {
while (k >= 0 && s1[k + 1] != s1[i])
k = pi[k];
if (s1[k + 1] == s1[i])
k++;
pi[i] = k;
}
k = -1;
for (int i = 1;i < m;i++) {
while (k >= 0 && s1[k + 1] != s2[i])
k = pi[k];
if (s1[k + 1] == s2[i])
k++;
if (k == n - 1) {
k = pi[n - 1];
cnt++;
if (cnt <= 1000)
ans[cnt] = i - n + 1;
}
}
fout << cnt << '\n';
for (int i = 1;i <= min(cnt, 1000);i++)
fout << ans[i] << " ";
return 0;
}