Cod sursa(job #2574322)
Utilizator | Ana Toader anamariatoader | Data | 5 martie 2020 21:33:42 |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 16 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.95 kb |
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int v[200005],l,n,nr,i,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;
for(j=1;j<=n;j++){
if(a[i]==s[j]){
i++;
if(i==l+1){
i=v[i-1];
nr++;
if(nr<=1000)
sol[nr]=j-l;
}
}
else{
i=v[i-1];
if(a[i]==s[j]){
i++;
}
}
}
fout<<nr<<'\n';
for(i=1;i<=nr;i++)
fout<<sol[i]<<' ';
return 0;
}