Cod sursa(job #1829194)

Utilizator stefanchistefan chiper stefanchi Data 14 decembrie 2016 15:51:54
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <cstring>
#define Nmax 2000003
using namespace std;
char search1[Nmax],pattern[Nmax];
int sufix[130],sol[1000],lim;

void sufix_creation()
{
    int i = 0, j = 1;
    while( j != strlen(pattern))
    {
        if(pattern[i] == pattern[j])
        {
            sufix[j] = i + 1;
            i++;
            j++;
        }
        else
        {
            while(pattern[i] != pattern[j] && i != 0)
                i--;
            if(pattern[i] != pattern[j])
            {
                sufix[j] = 0;
                j++;
            }
            else
            {
                sufix[j] = sufix[i];
                j++;
                i++;
            }
        }
    }
}

void read()
{
    freopen("kmp.in","r",stdin);
    freopen("kmp.out","w",stdout);
    scanf("%s %s",&pattern,&search1);
    sufix_creation();
}

void kmp()
{
    int j = 0;
    for(int i = 0 ; i < strlen(search1); i++)
    {
        if(pattern[j] == search1[i])
            j++;
        else
            j =  sufix[j];
        if(j == strlen(pattern))
        {
            sol[lim++]= i - j + 1;
            j = sufix[j - 1];
            if(lim > 1000)
                break;
        }
    }
}

void afisare()
{
    printf("%d\n",lim);
    for(int i= 0 ;  i< lim ; i++)
        printf("%d ",sol[i]);
}

int main()
{
    read();
    kmp();
    afisare();
    return 0;
}