Pagini recente » Cod sursa (job #2504232) | Cod sursa (job #2539969) | Cod sursa (job #679645) | Cod sursa (job #3335671) | Cod sursa (job #3321063)
#include <bits/stdc++.h>
#define NMAX 2000005
#define ll long long
#define mod 20173333
std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");
using namespace std;
int n, m, ans;
string a, b;
int lps[NMAX], sol[NMAX];
void init(){
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 kmp(){
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++;
}
if(ans==1000) break;
}
g << ans << '\n';
for(int i=1;i<=ans;i++)g << sol[i] << " ";
}
int main(){
f >> a;
f.get();
f >> b;
n=a.size(), m=b.size();
init();
kmp();
}