Cod sursa(job #2908498)

Utilizator FraNNNkieFrancesco-Gregorio Petrovici FraNNNkie Data 3 iunie 2022 22:25:14
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
void buildPrefixVect(string substring, vector <int>& prefArray){
    int sz = substring.size();
    //cout << sz;
    prefArray.resize(sz, 0);
    int i = 0, j = 1;
    while(i < sz && j < sz) {
        if(substring[i] == substring[j]) {
            prefArray[j] = i + 1;
            i++;
        } else {
            if(i > 0){
                i = prefArray[i - 1];
            }
        }
        j++;
    }
}
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    string substring, bigString;
    f >> substring;
    f >> bigString;
    int matches = 0;
    vector <int> startIndexes;
    vector <int> prefArray;
    buildPrefixVect(substring, prefArray);
    /*
    for(int i = 0; i < prefArray.size(); ++i) {
        cout << prefArray[i] << " ";
    }
    */
    int subStringPos = 0;
    int subStringSize = substring.size();
    int bigStringSize = bigString.size();
    for(int i = 0; i < bigStringSize; ++i) {
        if(substring[subStringPos] == bigString[i]) {
            subStringPos++;
            //am terminat de parcurs substringul

            if(subStringPos == subStringSize) {
                matches++;
                ///plus 1 pt ca subStringPos = lungimea substringului
                ///substringul este indexat de la 0 -> deci subStringPos este inafara arrayului
                if(matches < 1000) {
                    startIndexes.push_back(i - subStringPos + 1);
                }
                subStringPos = prefArray[subStringPos - 1];
            }
        } else {
            if(subStringPos > 0)
                subStringPos = prefArray[subStringPos - 1];
        }
    }
    g << matches << "\n";
    if(matches > 1000) {
        matches = 1000;
    }
    for(int i = 0; i < matches; ++i) {
        g << startIndexes[i] << " ";
    }
    f.close();
    g.close();
    return 0;
}