Cod sursa(job #2800704)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 13 noiembrie 2021 19:11:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

string a, b;
vector <int> solutions;
int lps[2000005];


int main()
{
    fin >> a >> b;
    a = " " + a;
    b = " " + b;

    lps[1] = 0;
    // build lps
    for (int i = 2; i < a.size(); i++)
    {
        char currLetter = a[i];
        // the current lps value
        int currIndex = lps[i - 1];
        
        while (currLetter != a[currIndex + 1] && currIndex != 0)
        {
            // get the prefix of the prefix of the prefix of the.... yes.
            currIndex = lps[currIndex];
        }

        int result = currIndex;
        if (currLetter == a[currIndex + 1])
        {
            // if letters match we increase the lps value by 1
            result++;
        }

        lps[i] = result;
    }

    int currIndex = 0;
    for (int i = 1; i < b.size(); i++)
    {
        char currLetter = b[i];
        while (currLetter != a[currIndex + 1] && currIndex != 0)
        {
            currIndex = lps[currIndex];
        }

        // currIndex is the length of the pattern
        if (currLetter == a[currIndex + 1])
        {
            currIndex++;
        }

        if (currIndex == a.size() - 1) // size - 1 beacause we did a = " " + a
        {
            solutions.push_back(i - a.size() + 1);
        }
    }

    // output to file
    fout << solutions.size() << '\n';
    for (int i = 0; i < 1000 && i < solutions.size(); i++)
    {
        fout << solutions[i] << ' ';
    }
    fout << '\n';
}