Pagini recente » Cod sursa (job #1695764) | Cod sursa (job #2362356) | Cod sursa (job #1536080) | Cod sursa (job #357584) | Cod sursa (job #731514)
Cod sursa(job #731514)
#include <cstdio>
#include <cctype>
#include <vector>
#define MAX 2000002
using namespace std;
vector<int>v;
char a[MAX],b[MAX];
int u[MAX],n,nr;
void prefix(){
int i,k;
u[0]=k=-1;
for(i=1;isalpha(a[i]);n=i++){
while(k>-1&&a[k+1]!=a[i])k=u[k];
if(a[k+1]==a[i])k++;
u[i]=k; }
}
void kmp(){
int i,k;
k=-1;
for(i=0;isalpha(b[i]);i++){
while(k>-1&&a[k+1]!=b[i])k=u[k];
if(a[k+1]==b[i])k++;
if(k==n){
nr++;
if(nr<1000)v.push_back(i-n);
k=u[k]; }
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,MAX,stdin);
fgets(b,MAX,stdin);
prefix();
kmp();
printf("%d\n",nr);
for(int i=0;i<v.size();i++)printf("%d ",v[i]);
}