Pagini recente » Cod sursa (job #2715671) | Cod sursa (job #680835) | Cod sursa (job #1103272) | Cod sursa (job #140910) | Cod sursa (job #259960)
Cod sursa(job #259960)
#include<iostream>
#include<fstream>
using namespace std;
int n,m,poz[2000001],rez[2000001],nr;
char a1[2000001],a2[2000001];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void prefix(){
int k=0;
for(int i=2;i<=n;i++){
while(k&&a1[k]!=a1[i+1])
k=poz[k];
if(a1[k+1]==a1[i])
k++;
poz[i]=k;
}
}
void numarare(){
int k=0;
for (int i=1;i<=m;i++){
while(k&&a1[k+1]!=a2[i])
k=poz[k];
if(a1[k+1]==a2[i])
k++;
if (k==n){
nr++;
if(nr<=1000)
rez[nr]=i-n;
k=poz[k];
}
}
}
void afisare(){
fout<<nr<<"\n";
if(nr>1000)
nr=1000;
for(int i=1;i<=nr;i++)
fout<<rez[i]<<" ";
fout<<"\n";
}
int main(){
fin>>a1>>a2;
n=strlen(a1)-1;
m=strlen(a2)-1;
prefix();
numarare();
afisare();
fin.close();
fout.close();
return 0;
}