Cod sursa(job #1836593)

Utilizator stefanchistefan chiper stefanchi Data 28 decembrie 2016 15:11:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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; i++)
    {
        while( j > 0 && sir[i] != pattern[j])
                j = sufix[j-1];
        if(pattern[j] == sir[i])
          j++;
        if(j == lim1)
            solutie.push_back(i- j + 1);
    }
}

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

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