Cod sursa(job #2444310)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 31 iulie 2019 09:41:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <string.h>
#include <fstream>
#include <vector>

using namespace std;

ifstream i("strmatch.in");
ofstream o("strmatch.out");

vector<int> v;

void computeLPSArray(string pat, int M, int lps[]);

void KMPSearch(string pat, string txt)
{
    int M = pat.length();
    int N = txt.length();

    int lps[M];

    computeLPSArray(pat, M, lps);

    int i = 0;
    int j = 0;
    while (i < N)
    {
        if (pat[j] == txt[i])
            j++, i++;

        if (j == M && v.size() < 1000)
            v.push_back(i - j), j = lps[j - 1];

        else if (i < N && pat[j] != txt[i])
        {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

void computeLPSArray(string pat, int M, int lps[])
{
    int len = 0;

    lps[0] = 0;

    int i = 1;
    while (i < M)
    {
        if (pat[i] == pat[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
                len = lps[len - 1];
            else
                lps[i] = 0, i++;
        }
    }
}

void print()
{
    o << v.size() << '\n';
    for(int i = 0 ; i < v.size() ; i++)
        o << v[i] << ' ';
}

int main()
{
    string txt;
    string pat;
    i >> pat;
    i >> txt;

    KMPSearch(pat, txt);
    print();

    return 0;
}