Cod sursa(job #2589311)

Utilizator NicuCNicu Capatina NicuC Data 26 martie 2020 09:39:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.49 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define LG_MAX 2000001

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char s[LG_MAX], p[LG_MAX];

int sol[1001], lps[LG_MAX], cnt, ccnt;

void computeLPSArray(char* pat, int M, int* lps);

void KMPSearch(char* pat, char* txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    // create lps[] that will hold the longest prefix suffix 
    // values for pattern 
    // Preprocess the pattern (calculate lps[] array) 
    computeLPSArray(pat, M, lps);

    int i = 0; // index for txt[] 
    int j = 0; // index for pat[] 
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }

        if (j == M) {
            //printf("Found pattern at index %d ", i - j);
            //cout << i - j << ' ';
            if (cnt <= 999) {
                cnt++;
                ccnt++;
                sol[cnt] = i - j;
            }
            else
            {
                ccnt++;
            }
            j = lps[j - 1];
        }

        // mismatch after j matches 
        else if (i < N && pat[j] != txt[i]) {
            // Do not match lps[0..lps[j-1]] characters, 
            // they will match anyway 
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
}

// Fills lps[] for given patttern pat[0..M-1] 
void computeLPSArray(char* pat, int M, int* lps)
{
    // length of the previous longest prefix suffix 
    int len = 0;

    lps[0] = 0; // lps[0] is always 0 

    // the loop calculates lps[i] for i = 1 to M-1 
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else // (pat[i] != pat[len]) 
        {
            // This is tricky. Consider the example. 
            // AAACAAAA and i = 7. The idea is similar 
            // to search step. 
            if (len != 0) {
                len = lps[len - 1];

                // Also, note that we do not increment 
                // i here 
            }
            else // if (len == 0) 
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int main()
{
    fin.getline(p, LG_MAX);
    fin.getline(s, LG_MAX);
    KMPSearch(p, s);
    fout << ccnt << '\n';
    for (int i = 1; i <= cnt; i++) {
        fout << sol[i] << ' ';
    }
}