Cod sursa(job #3318844)

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

using namespace std;

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

int main() {

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

    if(A.size() > B.size()){
        fout << 0;
    }else{
        int sizeA = A.size();
        int sizeB = B.size();

        int LPS[2000000];
        LPS[0] = -1;
        for(int indexStr = 1; indexStr < sizeA; indexStr++){
            int indexToLookAt = LPS[indexStr - 1];

            bool foundOne = false;
            while(!foundOne){
                if(A.at(indexStr) == A.at(indexToLookAt + 1)){
                    LPS[indexStr] = indexToLookAt + 1;
                    foundOne = true;
                }else{
                    if(indexToLookAt == -1)
                        break;
                    indexToLookAt = LPS[indexToLookAt];
                }
            }

            if(!foundOne)
                LPS[indexStr] = -1;
        }

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

                    if(counterSubsequences < 1000)
                        positions[counterSubsequences - 1] = i - sizeA + 1;
                }
            }else{
                if(indexA != 0) {
                    i--;
                    indexA = LPS[indexA - 1] + 1;
                }
            }
        }

        fout << counterSubsequences << "\n";
        for(int i = 0; i < min(counterSubsequences, 1001); i++)
            fout << positions[i] << " ";
    }

    return 0;
}