Cod sursa(job #1850724)

Utilizator Evghenii_BeriozchinEvghenii Beriozchin Evghenii_Beriozchin Data 18 ianuarie 2017 21:01:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
    string a,b;
long x[2000000], 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;
    while(i<a.length()){

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<b.length()){
    if (a[j]==b[i]) {if (j+1!=a.length()) {i++; j++;} else {rasp[n]=i-a.length()+1; n++; j=x[j];; i++;}} else if (j==0) i++; else j=x[j-1];

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