Cod sursa(job #2274467)

Utilizator veronicamicleVeronica Micle veronicamicle Data 1 noiembrie 2018 20:57:23
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <cstring>
#include <fstream>
#define Nmax 200005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int p[Nmax],v[Nmax];
void model(char b[Nmax],int lb)
{
    int j;
    j=0;
    for(int i=1;i<lb;i++)
    {
            while(j>0&&b[i]!=b[j])
                j=p[j-1];
            if(b[i]==b[j])
            {p[i]=j+1;
            j=j+1;
            }
    }

}
void kmp(char b[Nmax],char a[Nmax],int &nr,int la,int lb)
   {
       int j=0;
       for(int i=0;i<la;i++)
       {
           while (j>0&&a[i]!=b[j])
            j=p[j-1];
           if(a[i]==b[j])
           {
            j=j+1;
           }
           if(j==strlen(b))
           {
             nr++;
             if(nr<=1000)
            v[nr]=i-lb+1;
            }
       }
   }
int main()
{
    char a[Nmax],b[Nmax];
    int nr=0,la,lb;
    f>>a>>b;
    la=strlen(a);
    lb=strlen(b);
    model(b,lb);
    kmp(b,a,nr,la,lb);
    g<<nr<<endl;
    for(int i=1;i<=nr&&i<=1000;i++)
        g<<v[i]<<" ";
    return 0;
}