Cod sursa(job #1836545)

Utilizator stefanchistefan chiper stefanchi Data 28 decembrie 2016 14:33:00
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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
        {
            if(i > 0)
                i = sufix[i-1];
            else
            {
                sufix[j] = 0;
                j++;
                i=0;
            }
        }
    }
}

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;
}