Cod sursa(job #1598878)

Utilizator gorni97aaa aaa gorni97 Data 13 februarie 2016 13:57:00
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define maxn 2000003
using namespace std;
char a[maxn],b[maxn];
int p[maxn];
int main()


{int n,m,i,j,OK,q,nr,v[1000],k;

fstream f("strmatch.in",ios::in);
fstream g("strmatch.out",ios::out);
f.getline(a,maxn,'\n');
f.getline(b,maxn,'\n');
n=strlen(a);
m=strlen(b);

p[0]=0;

 for(i=1;i<n;i++)
 {OK=0;q=0;
     for(j=0;((j<=i)&&(OK==0));j++)
    if(a[i+q]==a[j])
 q++;
 else
 {OK=1;p[i]=q;}

 }

nr=0;

i=0;
while(i<m)
{k=i;
j=0;
while((a[j]==b[k])&&(j<n))
{j++;k++;
if(j==n)
{nr++;
v[nr]=i;}
}
i=i+p[j-1]+1;

}

g<<nr<<'\n';
for(i=1;i<=nr;i++)
    g<<v[i]<<" ";

    f.close();
    g.close();
}