Mai intai trebuie sa te autentifici.
Cod sursa(job #2319244)
Utilizator | Data | 13 ianuarie 2019 20:54:59 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 52 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.92 kb |
#include <fstream>
#include <string>
#define MAX 2000004
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int na,nb,i,j,x[MAX],y[MAX];
string a,b;
void chestie(){
for (i=2;i<=na;i++){
while (j && a[j+1]!=a[i])
j=x[j];
if (a[j+1]==a[i])
j++;
x[i]=j;
}
}
int main(){
fin>>a>>b;
na=a.length();
nb=b.length();
for (i=na-1;i>=0;i--)
a[i+1]=a[i];
for (i=nb-1;i>=0;i--)
b[i+1]=b[i];
chestie();
for (i=1;i<=nb;i++){
while (j && a[j+1]!=b[i])
j=x[j];
if (a[j+1]==b[i])
j++;
if (j==na){
j=x[j];
y[0]++;
y[y[0]]=i-na+1;
}
}
fout<<y[0]<<'\n';
y[0]=min(y[0],1000);
for (i=1;i<=y[0];i++)
fout<<y[i]-1<<" ";
fin.close();
fout.close();
return 0;
}