Cod sursa(job #3142136)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 19 iulie 2023 14:40:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <string.h>
#include <vector>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n, m, T[10005];
char S[10005], W[10005];
vector<int> V;

void Prep(int m, char W[], int T[])
{
    int lg = 0;

    int i = 1;
    while(i < m)
    {
        if(W[i] == W[lg]){
            lg ++;
            T[i ++] = lg;
        }

        else{
            if(lg)
                lg = T[lg - 1];
            else
                T[i ++] = 0;
        }
    }
}

void KMPSearch(char S[], char W[])
{
    n = strlen(S);
    m = strlen(W);

    Prep(m, W, T);

    int i, j; i = j = 0;
    while((n - i) >= (m - j))
    {
        if(S[i] == W[j])
            j ++, i ++;

        if(j == m){
            if(V.size() < 1000)
                V.push_back(i - j);
            j = T[j - 1];
        }

        else if(i < n && W[j] != S[i]){
            if(j)
                j = T[j - 1];
            else
                i ++;
        }
    }
}

int main()
{
    f >> W >> S;
    KMPSearch(S, W);

    g << V.size() << '\n';
    for(int i = 0; i < V.size(); i ++)
        g << V[i] << " ";
    return 0;
}