Cod sursa(job #3318829)

Utilizator raul41917raul rotar raul41917 Data 29 octombrie 2025 11:12:21
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <queue>
#include <string>

using namespace std;

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

/**
 * Longest prefix that is also a suffix
 * it is kind of a bit misleading isn't it because you don't do it for the word as a whole
 * but instead you do it for the word that is until that letter
 * so for a word A, for each of the letter Ai you 'segment' it until the specific character
 * and then there you look for the word that ends at the specific character for the prefix that
 * is also a suffix
 */

void createLPS(string pattern, int LPS[]){
    LPS[0] = -1;
    for(int indexStr = 1; indexStr < pattern.size(); indexStr++){
        int indexToLookAt = LPS[indexStr - 1] + 1;

        if(pattern.at(indexStr) == pattern.at(indexToLookAt))
            LPS[indexStr] = indexToLookAt;
        else
            LPS[indexStr] = -1;
    }
}

int main() {

    string A, B;
    fin >> A >> B;

    if(A.size() > B.size()){
        fout << 0;
    }else{
        int LPS[2000000];
        createLPS(A, LPS);

        int indexA = 0;
        int counterSubsequences = 0;
        queue<int> positions;
        for(int i = 0; i < B.size(); i++){
            if(A.at(indexA) == B.at(i)){
                indexA++;
                if(indexA == A.size()){
                    counterSubsequences++;
                    indexA = LPS[indexA - 1] + 1;

                    if(positions.size() < 1000)
                        positions.push(i - A.size() + 1);
                }
            }else{
                indexA = LPS[indexA] + 1;
                if(indexA != 0)
                    i--;
            }
        }

        fout << counterSubsequences << endl;
        while(!positions.empty()){
            fout << positions.front() << " ";
            positions.pop();
        }
    }

    return 0;
}