Cod sursa(job #2311627)

Utilizator crion1999Anitei cristi crion1999 Data 3 ianuarie 2019 15:16:09
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

string patern;
string text;
int longestPrefixSufix[NMAX];
vector<int> result;
int N,M;

void ComputeLongestPrefixSufixArray()
{
    int len = 0;
    longestPrefixSufix[0] = 0;
    longestPrefixSufix[1] = 0;
    for(int i = 2; i < M;++i)
    {
        while(len > 0 && patern[len] != patern[i])
            len = longestPrefixSufix[len-1];

        if(patern[len] == patern[i])
            len++;

        longestPrefixSufix[i] = len;
    }
}

void KMP()
{
    for(int i = 0, j = 0; i < N;++i)
    {
        while( j > 0 && patern[j] !=text[i])
            j = longestPrefixSufix[j-1];

        if(patern[j] == text[i])
            j++;

        if(j == M)
        {
            result.push_back(i-j + 1);
            j = longestPrefixSufix[j-1];
        }
    }
}

int main()
{
    getline(fi,patern);
    getline(fi, text);
    fi.close();
    N = text.length();
    M = patern.length();

    ComputeLongestPrefixSufixArray();

    KMP();

    fo<<result.size();
    fo<<"\n";
    for(auto y:result)
        fo<<y<<" ";


    fo.close();
}