Cod sursa(job #2311583)

Utilizator crion1999Anitei cristi crion1999 Data 3 ianuarie 2019 14:05:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 2000000
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;
    for(int i = 1; i < M;)
    {
        if(patern[len] == patern[i])
        {
            len++;
            longestPrefixSufix[i] = len;
            i++;
        }
        else if(patern[len] != patern[i])
        {
            if(len != 0)
                len = longestPrefixSufix[len - 1];
            else if(len == 0)
            {
                longestPrefixSufix[i] = 0;
                i++;
            }
        }
    }
}
void KMP()
{
    for(int i = 0, j = 0; i <= N;)
    {
        if(patern[j] == text[i])
        {
            j++;
            i++;
            if(j == M)
            {
                result.push_back(i-j);
                j = longestPrefixSufix[j-1];
            }
        }
        else if(patern[j] != text[i])
        {
            if(j == 0)
                i++;
            else if(j != 0)
            {
                j = longestPrefixSufix[j - 1];
            }
        }
    }
}

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

    ComputeLongestPrefixSufixArray();

    KMP();

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