Pagini recente » Cod sursa (job #2173664) | Cod sursa (job #993933) | Cod sursa (job #2323766) | Cod sursa (job #910502) | Cod sursa (job #1953419)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int maxn = 2e6 + 5;
int Next[maxn];
void Prefix (string Pattern, int m) {
int x = 0, i;
Next[0] = 0;
for (i = 2; i <= m; i++) {
while (x > 0 && Pattern[x + 1] != Pattern[i]) x = Next[x];
if (Pattern[x + 1] == Pattern[i]) x++;
Next[i] = x;
}
}
void KMP (string Str, string Pattern, int n, int m) {
vector <int> Ans;
int i, x = 0;
Prefix(Pattern, m);
for (i = 1; i <= n; i++) {
while (x > 0 && Pattern[x + 1] != Str[i]) x = Next[x];
if (Pattern[x + 1] == Str[i]) x++;
if (x == m) {
Ans.push_back(i - m);
x = Next[x];
}
}
fout << Ans.size() << "\n";
n = min(1000, (int) Ans.size() );
for (i = 0; i < n; i++) {
fout << Ans[i] << " ";
}
fout << "\n";
}
int main () {
ios_base :: sync_with_stdio (false);
string A, B;
fin >> A >> B;
int n = (int) B.size();
int m = (int) A.size();
A = "#" + A;
B = "#" + B;
KMP(B, A, n, m);
fin.close();
fout.close();
return 0;
}