Pagini recente » Cod sursa (job #2707463) | Cod sursa (job #2779803) | Cod sursa (job #2627184) | Cod sursa (job #2738821) | Cod sursa (job #2857606)
#include <bits/stdc++.h>
#include <fstream>
#define MAX 2000005
#define pb push_back
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[MAX],b[MAX];
int M,N,p[MAX],pos[1001];
void cit(){
f.getline(a,MAX);
f.getline(b,MAX);
}
void prefix(){
int k=0;
p[1]=0;
for(int i=2;i<=M;i++){
while(k && a[k+1]!=a[i])
k=p[k];
if(a[k+1]==a[i])
k++;
p[i]=k;
}
}
//void afis(){
// for(int i=n;i>=1;i--)
// g<<sol[i]<<' ';
//}
int main()
{
int k=0,n=0;
cit();
M=strlen(a);
N=strlen(b);
for(int i=M;i;i--)a[i]=a[i-1]; a[0]=' ';
for(int i=N;i;i--)b[i]=b[i-1]; b[0]=' ';
prefix();
for(int i=1;i<=N;i++){
while(k && a[k+1]!=b[i])
k=p[k];
if(a[k+1]==b[i])
k++;
if(k==M){
k=p[M];
n++;
if(n<=1000)
pos[n]=i-M;
}
}
g<<n<<'\n';
for(int i=1;i<=min(n,1000);i++)
g<<pos[i]<<" ";
return 0;
}