Pagini recente » Rezultatele filtrării | Cod sursa (job #1313406) | Cod sursa (job #1160422) | Cod sursa (job #2761547) | Cod sursa (job #1953404)
#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 = -1, i;
Next[0] = 0;
for (i = 1; 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) {
vector <int> Ans;
int n = (int) Str.size();
int m = (int) Pattern.size();
int i, x = -1;
Prefix(Pattern, m);
for (i = 0; i < n; i++) {
while (x > 0 && Pattern[x + 1] != Str[i]) x = Next[x];
if (Pattern[x + 1] == Str[i]) x++;
if (x == m - 1) {
Ans.push_back(i - m + 1);
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;
KMP(B, A);
fin.close();
fout.close();
return 0;
}