Cod sursa(job #1879563)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 14 februarie 2017 23:38:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LENGTH_MAX 2000005

using namespace std;

char str[LENGTH_MAX];
char pattern[LENGTH_MAX];

int pi[LENGTH_MAX], M, N;

void Prefix()
{
    int len=strlen(pattern);

    pi[1]=0;
    int k=0;

    for(int q=2; q <= len; ++q)
    {
        while(k>0 && pattern[k+1]!=pattern[q])
            k=pi[k];

        if(pattern[k+1]==pattern[q])
            ++k;

        pi[q]=k;
    }
}

int potriv;
int poz[LENGTH_MAX];

void KMP()
{
    int q=0;

    for(int i=1; i<=N; ++i)
    {
        while(q>0 && pattern[q+1]!=str[i])
            q=pi[q];

        if(pattern[q+1]==str[i])
            ++q;

        if(q==M)
        {
            ++potriv;
            if(potriv<=1000)
                poz[potriv]=i-M;
            else
                break;
        }
    }

    cout<<potriv<<"\n";

    for(int i=1; i<=min(potriv,1000); ++i)
        cout<<poz[i]<<" ";

}

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

    scanf("%s\n", &pattern);
    scanf("%s", &str);
    M=strlen(pattern);
    N=strlen(str);
    int i;

    for (i = M; i; --i)
        pattern[i] = pattern[i-1];

    pattern[0] = ' ';

    for (i = N; i; --i) str[i] = str[i-1];
        str[0] = ' ';

    pattern[M+1]=0;
    str[N+1]=0;

    Prefix();

    KMP();

    return 0;
}