Pagini recente » Cod sursa (job #423621) | Cod sursa (job #904495) | Cod sursa (job #278683) | Cod sursa (job #2720273) | Cod sursa (job #2449854)
#include <iostream>
#include <fstream>
#include <cstring>
#define minim(a, b) ((a < b) ? a : b)
#define MAXN 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[MAXN],b[MAXN];
int n,m;
int pi[MAXN],pos[1024];
void pref(){
int q=0;
pi[1]=0;
for(int i=2;i<=m;i++){
while(q and a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
q++;
pi[i]=q;
}
}
int main(){
int q=0,N=0;
fin.get(a,MAXN);
fin.get();
fin.get(b,MAXN);
for(; (a[m]>='A' and a[m]<='Z') || (a[m]>='a' and a[m]<='z') || (a[m]>='0' and a[m]<='9');m++);
for(; (b[n]>='A' and b[n]<='Z') || (b[n]>='a' and b[n]<='z') || (b[n]>='0' and b[n]<='9');n++);
for(int i=m;i!=0;i--)
a[i]=a[i-1];
a[0]=' ';
for(int i=n;i;i--)
b[i]=b[i-1];
b[0]=' ';
pref();
for(int i=1;i<=n;i++){
while(q and a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
q++;
if(q==m){
q=pi[m];
N++;
if(N<=1000)
pos[N]=i-m;
}
}
fout<<N<<'\n';
for(int i=1;i<=minim(N,1000);i++)
fout<<pos[i]<<' ';
return 0;
}