Pagini recente » Cod sursa (job #267669) | Cod sursa (job #2355853) | Cod sursa (job #659599) | Cod sursa (job #474065) | Cod sursa (job #3321089)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, ans;
string a, b;
int lps[2000005], sol[2000005];
void initLPS() {
int i = 1, lg = 0;
while (i < n) {
if (a[i] == a[lg]) {
lg++;
lps[i++] = lg;
} else {
if (lg) lg = lps[lg - 1];
else lps[i++] = 0;
}
}
}
void kmpSearch() {
int i = 0, lg = 0;
while (i < m) {
if (b[i] == a[lg]) {
i++;
lg++;
if (lg == n) {
sol[++ans] = i - lg;
lg = lps[lg - 1];
}
} else {
if (lg) lg = lps[lg - 1];
else i++;
}
}
g << ans << '\n';
for (int i=1;i<=min(ans, 1000);i++) g<<sol[i]<<" ";
}
int main() {
f >>a;
f.get();
f >>b;
n=a.size();
m=b.size();
initLPS();
kmpSearch();
return 0;
}