Pagini recente » Cod sursa (job #203637) | Cod sursa (job #409299) | Cod sursa (job #1851508) | Cod sursa (job #1239437) | Cod sursa (job #2675052)
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int p[NMAX];
char a[NMAX], b[NMAX];
int sol[1005];
void citire(){
f.getline(a+1, NMAX);
f.getline(b+1, NMAX);
}
void form_prefix(){
int k=0;
int m=strlen(a+1);
p[1] = 0;
for(int j=2; j<=m; j++){
while(k>0 && a[k+1] != a[j])
k = p[k];
if(a[k+1] == a[j]){
k++;
}
p[j] = k;
}
}
int match_strings(){
int k=0;
int nr=0;
int n=strlen(b+1);
int m=strlen(a+1);
for(int i=1; i<=n; i++){
while(k>0 && a[k+1] != b[i])
k = p[k];
if(b[i] == a[k+1])
k++;
if(k==m){
nr++;
if(nr<=1000)
sol[nr] = i-m;
k=p[k];
}
}
return nr;
}
void afisare(int nr){
g<<nr<<'\n';
nr = min(nr, 1000);
for(int i=1; i<=nr; i++)
g<<sol[i]<<' ';
}
int main()
{
citire();
form_prefix();
int nr = match_strings();
afisare(nr);
return 0;
}