Pagini recente » Cod sursa (job #624309) | Cod sursa (job #2244522) | Cod sursa (job #856345) | Cod sursa (job #423491) | Cod sursa (job #3216609)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 4e6;
int kmp[5 + nmax];
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
fin >> a >> b;
b = "#" + a + "#" + b;
for (int i = 2; i < (int)b.size(); i++) {
int pos = kmp[i - 1];
while (pos > 0 && b[pos + 1] != b[i])
pos = kmp[pos];
if (b[pos + 1] == b[i])
kmp[i] = pos + 1;
}
int cnt = 0;
for (int i = a.size() + 2; i < (int)b.size(); i++)
if (kmp[i] == (int)a.size())
cnt++;
fout << cnt << '\n';
cnt = 0;
for (int i = a.size() + 2; i < (int)b.size(); i++)
if (kmp[i] == (int)a.size()) {
fout << i - (int)a.size() * 2 - 1 << ' ';
cnt++;
if (cnt == 1000)
break;
}
fout << '\n';
return 0;
}