Pagini recente » Cod sursa (job #3236400) | Cod sursa (job #2985614) | Cod sursa (job #3356954) | Cod sursa (job #1508134) | Cod sursa (job #3321435)
#include <bits/stdc++.h>
#define NMAX 2000005
#define ll long long
std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");
using namespace std;
int n, m, ans;
int sol[NMAX], lps[NMAX];
string a, b;
void init(){
int lg=0, i=1;
while(i<m){
if(b[i]==b[lg]) lps[i++]=++lg;
else{
if(lg) lg=lps[lg-1];
else lps[i++]=0;
}
}
}
void kmp(){
int i=0, lg=0;
while(i<n){
if(a[i]==b[lg]){
lg++;
i++;
if(lg==m) 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() {
getline(f, b);
getline(f, a);
n=a.size();
m=b.size();
init();
kmp();
}