Cod sursa(job #2511063)

Utilizator mafteidanutMaftei Danut mafteidanut Data 18 decembrie 2019 00:08:15
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define Nmax 200000

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

char pattern[Nmax],sir[Nmax];
int p[Nmax];

void READ()
{
    fin>>pattern;
    fin>>sir;

}

void pre_suf()
{
    int j=0;

    for(int i=1;i<strlen(pattern);++i)
        {
            if(pattern[i]==pattern[j])
    {

        p[i]=p[i-1]+1;
        j++;
    }
    else{
        while(pattern[i]!=pattern[j] && j!=0)
        {
            j=p[j-1];
        }

        if(pattern[i]==pattern[j])
            {

        p[i]=p[j]+1;
        j++;
          }
    }
        }
}

void solution()
{

    int sol[Nmax];
    int k=0;
    int j=0;

    for(int i=0;i<strlen(sir);++i)
    {


    if(j==(int)strlen(pattern))
        {sol[++k]=i-j;
        j=p[j-1];
        }

        if(sir[i]==pattern[j])
           {
               j++;
           }
            else if(j!=0){
                   while(sir[i]!=pattern[j] && j!=0)
                        j=p[j];
                if(sir[i]==pattern[j])j++;
            }
     if(k==1000)break;

    }
    fout<<k<<"\n";
    for(int i=1;i<=k;++i)
        fout<<sol[i]<<" ";
}
int main()
{
    READ();
    pre_suf();
    solution();

    return 0;
}