Cod sursa(job #1836015)

Utilizator stefanchistefan chiper stefanchi Data 27 decembrie 2016 18:17:19
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <cstring>
#include <cstdio>
#define Nmax 2000005
#include <vector>
using namespace std;
char sir[Nmax];
char pattern[Nmax];
vector <int> solutie;
int sufix[Nmax];
int lim1,lim2;

void prepare()
{
    int i = 0 , j = 1;
    while(j < lim1)
    {
        if(pattern[i] == pattern[j])
        {
            sufix[j] = i +1;
            i++;
            j++;
        }
        else
        {
            int ok = 0 ;
            while( i >= 0 && pattern[i] != pattern[j])
            {
                i--;
                if(pattern[i] == pattern[j])
                    ok = 1;
            }
            if(ok == 1)
                sufix[j] = i+1;
            else
            {
                sufix[j] = 0;
            }
            i++;
            j++;
        }
    }
}

void kmp()
{
    int j = 0 ;
    for(int i = 0 ; i < lim2; )
    {
        if(pattern[j] == sir[i])
           {
               j++;
               i++;
           }
        else
        {
            if(j != 0)
                j = sufix[i];
            else
                i++;
        }
        if(j == lim1)
        {
            if(solutie.size() == 1000)
                    return;
            solutie.push_back(i - lim1);
            i--;
            j = 0;
        }
    }

}

void afisare()
{
    printf("%d\n",solutie.size());
    for(vector <int> :: iterator it =  solutie.begin() ; it != solutie.end() ; it++)
        printf("%d ",*it);
}

void read()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",&pattern,&sir);
    lim1= strlen(pattern);
    lim2= strlen(sir);
    prepare();
    kmp();
}
int main()
{
    read();
    afisare();
    return 0;
}