Pagini recente » Cod sursa (job #1554388) | Cod sursa (job #2302780) | Cod sursa (job #2324184) | Cod sursa (job #1943186) | Cod sursa (job #2319249)
#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(){
int j=0;
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;
}