Cod sursa(job #1915545)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 8 martie 2017 21:34:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <cstdio>
#include <cstring>

#define lim 1000

using namespace std;

const int NMax = 2000005;

char pattern[NMax], sir[NMax];
int pi[NMax];
int lenp, lens;

void Prefix()
{
    pi[1]=0;
    int j=0;

    for(int i=2; i<=lenp; ++i)
    {
        while(j>=1 && pattern[i]!=pattern[j+1])
            j=pi[j];

        if(pattern[j+1]==pattern[i])
            ++j;

        pi[i]=j;
    }
}

int matches;
int match[NMax];

void KMP()
{
    int j=0;

    for(int i=1; i<=lens; ++i)
    {
        while(j>=1 && pattern[j+1]!=sir[i])
            j=pi[j];

        if(sir[i]==pattern[j+1])
            ++j;

        if(j == lenp)
        {
            ++matches;
            if(matches <= lim)
                match[matches]=i-lenp;
        }

    }

    printf("%d\n", matches);

    for(int i=1; i<=min(matches, lim); ++i)
        printf("%d ", match[i]);
}


int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s\n", &pattern);
    scanf("%s", &sir);

    lenp=strlen(pattern);
    lens=strlen(sir);

    for(int i=lenp; i>=1; --i)
        pattern[i]=pattern[i-1];

    for(int i=lens; i>=1; --i)
        sir[i]=sir[i-1];

    Prefix();

    KMP();

    return 0;
}