Pagini recente » Cod sursa (job #1283301) | Cod sursa (job #1232181) | Cod sursa (job #2263006) | Cod sursa (job #657482) | Cod sursa (job #2231491)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int maxn=2000004;
char sirA[maxn],sirB[maxn];
int M,N,pi[maxn],pos[1026];
void prefix(){
int i,q=0;
for(i=2,pi[1]=0;i<=M;++i){
while(q&&sirA[q+1]!=sirA[i])
q=pi[q];
if(sirA[q+1]==sirA[i])
++q;
pi[i]=q;
}
}
int main(){
fin.getline(sirA,maxn);
fin.getline(sirB,maxn);
int q=0,n=0,i;
for(;(sirA[M]>='A'&&sirA[M]<='Z')||(sirA[M]>='a'&&sirA[M]<='z')||(sirA[M]>='0' &&sirA[M]<='9');++M);
for(;(sirB[N]>='A'&&sirB[N]<='Z')|| (sirB[N]>='a'&&sirB[N]<='z')||(sirB[N]>='0' &&sirB[N]<='9');++N);
for(i=M;i;--i)sirA[i]=sirA[i-1];sirA[0]=' ';
for(i=N;i;--i)sirB[i]=sirB[i-1];sirB[0]=' ';
prefix();
for(i=1;i<=N;++i){
while(q&&sirA[q+1]!=sirB[i])
q=pi[q];
if(sirA[q+1]==sirB[i])
++q;
if(q==M){
q=pi[M];
++n;
if(n<=1000)
pos[n]=i-M;
}
}
fout<<n<<'\n';
for(i=1;i<=min(n,1000);++i)
fout<<pos[i]<<' ';
return 0;
}