Cod sursa(job #2194591)

Utilizator adc98Adam Cristian adc98 Data 13 aprilie 2018 20:02:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char p[2000001],s[2000001];
int failure[2000005];

int sol[100001],nrElemente=0;

void determinareEsec()
{
    int k=-1;
    int lg=strlen(p);
    failure[0]=-1;
    for(int i=1;i<=lg;++i)
        {
         while(k>=0 && p[k]!=p[i-1]) k=failure[k];
         k++;
         failure[i]=k;
        }
    for(int i=1;i<=lg;++i) failure[i-1]=failure[i];
}

void KMP()
{
    int lg_s=strlen(s),lg_p=strlen(p);

    /*int i=0,k=0;
    while(i<lg_s)
        {
         while( k>=0 && s[i]!=p[k] ) k=failure[k];
         if(k==strlen(p)-1)
            {
             sol[nrElemente++]=i-lg_p+1;
             i++;
            }
          else
            {
             i++;
             k++;
            }

        }*/

    int i=0,j=0;
    while(i<lg_s)
        {
         if(s[i]==p[j])
            {
             i++;
             j++;
            }
         if(j==lg_p)
            {
             sol[nrElemente++]=i-j;
             j=failure[j-1];
            }
          else
            {
             if(i<lg_s && s[i]!=p[j])
                {
                 if(j>0) j=failure[j-1];
                  else i++;
                }
            }
        }
}


int main()
{
    fin.getline(p,2000001);
    fin.getline(s,2000001);
    determinareEsec();
    KMP();
    fout<<nrElemente<<"\n";
    for(int i=0;i<nrElemente;++i) fout<<sol[i]<<" ";
    return 0;
}