Cod sursa(job #2365951)

Utilizator crion1999Anitei cristi crion1999 Data 4 martie 2019 17:36:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda pregatire_cls12_oji Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

int N, M;
int longestPrefixSuffix[2000005];
string patern, str;

vector<int> rez;


void ComputeLPS()
{
    int len = 0;
    longestPrefixSuffix[0] = 0;

    for(int i = 1; i < patern.size();)
    {
        if(patern[len] == patern[i])
        {
            len++;
            longestPrefixSuffix[i] = len;
            i++;
        }
        else
        {
            if(len != 0)
                len = longestPrefixSuffix[len - 1];
            else
            {
                longestPrefixSuffix[i] = 0;
                ++i;
            }
        }
    }
}

int main()
{
    getline(fi, patern);
    getline(fi, str);

    ComputeLPS();

    for(int i = 0, j = 0; i < str.size();)
    {
        if(patern[j] == str[i])
        {
            i ++;
            j ++;

            if(j == patern.size())
            {
                rez.push_back(i - j);
                j = longestPrefixSuffix[j - 1];
            }
        }
        else
        {
            if(j == 0)
                i++;
            else
                j = longestPrefixSuffix[j - 1];
        }
    }

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

}