Cod sursa(job #1850735)

Utilizator Evghenii_BeriozchinEvghenii Beriozchin Evghenii_Beriozchin Data 18 ianuarie 2017 21:13:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
    string a,b;
long x[2000005], rasp[1005];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
    fin>>a;
    fin>>b;
    x[0]=0;
   long n=0,i=1,j=0;
   long alen=a.length();
   long blen=b.length();
    while(i<alen){

if (a[i]==a[j]) {  x[i]=j+1;  i++; j++;}
       else if (j==0) {x[i]=0; i++;}
            else j=x[j-1];
    }
   i=0; j=0;
   while (i<blen){
    if (a[j]==b[i]) {if (j+1!=alen) {i++; j++;} else {if (n<1000) rasp[n]=i-alen+1; n++; j=x[j];; i++;}} else if (j==0) i++; else j=x[j-1];

   }
   fout<<n<<endl;
   if (n>0)
   for (int k=0; (k<n && k<1000); k++)
    fout<<rasp[k]<<" ";
    return 0;
}