Cod sursa(job #2574446)
Utilizator | Ana Toader anamariatoader | Data | 5 martie 2020 22:23:45 |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 40 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.91 kb |
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int v[2000005],l,n,nr,i,k,j,sol[1005];
char a[2000005],s[2000005];
int main(){
fin>>(a+1)>>(s+1);
l=strlen(a+1);
n=strlen(s+1);
j=1; i=2;
v[0]=v[1]=1;
while(i<=l){
if(a[i]==a[j]){
v[i]=j+1;
i++;
j++;
}
else{
v[i]=1;
j=v[i-1];
i++;
}
}
i=1,j=1;
while(i<=n){
if(a[j]==s[i]){
if(j==l){
nr++;
if(nr<=1000)
sol[nr]=i-l;
}
i++;
j++;
}
else{
if(j>1)
j=v[j-1];
else
i++;
}
}
fout<<nr<<'\n';
for(i=1;i<=nr;i++)
fout<<sol[i]<<' ';
return 0;
}