Pagini recente » Cod sursa (job #1855840) | Mihnea Andreescu | Cod sursa (job #2852076) | Cod sursa (job #2169108) | Cod sursa (job #146046)
Cod sursa(job #146046)
#include<fstream>
using namespace std;
#define Nmax 2000005
char A[Nmax], B[Nmax];
int pi[Nmax];
int poz[1024];
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin>>A>>B;
int sol = 0;
pi[0] = -1;
int k = -1,L;
for(int i=1;A[i];i++){
while(k>=0 && A[k+1] != A[i])
k = pi[k];
if(A[k+1] == A[i])
k++;
pi[i] = k;
L = i;
}
L++;
k=-1;
for(int i=0;B[i];i++){
while(k>=0 && A[k+1] != B[i])
k = pi[k];
if(A[k+1] == B[i])
k++;
if(k == L-1){
sol++;
if(sol <= 1000)
poz[sol] = i-L+1;
k = pi[k];
}
}
fout<<sol<<"\n";
for(int i=1;i<=((sol>1000)?1000:sol); i++)
fout<<poz[i]<<" ";
fin.close();
fout.close();
return 0;
}