Cod sursa(job #2311632)

Utilizator crion1999Anitei cristi crion1999 Data 3 ianuarie 2019 15:23:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

char patern[NMAX];
char text[NMAX];
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+1] != patern[i])
            len = longestPrefixSufix[len];

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

        longestPrefixSufix[i] = len;
    }
}

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

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

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

int main()
{
    fi>>(patern+1);
    fi>>(text+1);
    fi.close();
    N = strlen(text+1);
    M = strlen(patern+1);

    ComputeLongestPrefixSufixArray();

    KMP();

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


    fo.close();
}