Pagini recente » Diferente pentru olimpici intre reviziile 127 si 128 | Profil Erioanacioara | Diferente pentru olimpici intre reviziile 56 si 180 | Cod sursa (job #1346645) | Cod sursa (job #1219996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int last[2000010], nr;
vector<int> sol;
string a, b;
void pref() {
int k = 0;
last[1] = 0;
for (int i = 2; i < a.length(); i++) {
while (k > 0 && a[k+1] != a[i]) k = last[k];
if (a[k+1] == a[i]) k++;
last[i] = k;
}
}
void kmp() {
int k = 0;
for (int i = 1; i < b.length(); i++) {
while (k > 0 && a[k+1] != b[i]) k = last[k];
if (a[k+1] == b[i]) {
k++;
if (k == a.length() - 1) {
nr++;
if (nr <= 1000) {
sol.push_back(i - a.length() + 1);
}
k = last[k];
}
}
}
}
int main() {
int x, y;
f >> a;
f >> b;
a = " " + a;
b = " " + b;
pref();
kmp();
g << nr << endl;
for (int i = 0; i < sol.size(); i++) {
g << sol[i] << " ";
}
return 0;
}