Cod sursa(job #2311693)

Utilizator crion1999Anitei cristi crion1999 Data 3 ianuarie 2019 16:30:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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;

void ComputeLongestPrefixSufixArray()
{
    int len = 0;
    longestPrefixSufix[0] = 0;
    for(int i = 1; i < patern.length();++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 < text.length();)
    {
        if(patern[j] == text[i])
        {
            j++;
            i++;
            if(j == patern.length())
            {
                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);

    ComputeLongestPrefixSufixArray();

    KMP();

    fo<<result.size();
    fo<<"\n";
    int k = 0;
    for(auto y:result)
    {
        if(k == 1000)
            break;
        fo<<y<<" ";
        k++;
    }
}