Cod sursa(job #2063226)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 11 noiembrie 2017 10:18:21
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("kmp.in");
ofstream fout("kmp.out");

const int NMax = 2000005;
const int maxi = 1000;
char s[NMax], s1[NMax];
int prefixe[NMax];

void Prefix()
{
    int i=1, j=0;
    prefixe[0] = 0;
    int n = strlen(s);
    while(i < n)
    {
        while(j > 0 && s[j] != s[i])
            j = prefixe[j-1];

        if(s[j] == s[i])
            ++j;

        prefixe[i] = j;
        ++i;
    }
}

void KMP()
{
    int n = strlen(s);
    int m = strlen(s1);
    int j = 0;
    int potriviri = 0;
    int potriv[maxi+5];

    for(int i=0; i<m; ++i)
    {
        while(j > 0 && s[j]!=s1[i])
            j = prefixe[j-1];

        if(s[j] == s1[i])
            ++j;

        if(j == n)
        {
            ++potriviri;
            if(potriviri <= maxi)
                potriv[potriviri] = i - n + 1;

        }
    }

    fout << potriviri << "\n";

    for(int i=1; i<=min(maxi,potriviri); ++i)
        fout << potriv[i] << " ";
}

int main()
{
    fin >> s;
    fin >> s1;
    Prefix();
    KMP();
    return 0;
}