Cod sursa(job #2891098)

Utilizator DMR6476Erdic Dragos DMR6476 Data 17 aprilie 2022 15:40:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <iostream>
#include<cstring>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char theFirstArray[2000001];
char theSecondArray[2000001];
int dpOfFirst[2000001];
// first array is the array which you check if it's in the second array
void preProcessing(char theArray[], int sizeOfArray){
    dpOfFirst[0] = 0;
    for(int i = 1; i < sizeOfArray; i++){
        int lastPos = dpOfFirst[i - 1];
        if(lastPos == 0){
            // case AA
            if(theArray[i] == theArray[lastPos]){
                dpOfFirst[i] = 1;
            }
            // case AB
            else{
                dpOfFirst[i] = 0;
            }
        }
        else{ // you found something that is equal to this
            if(theArray[i] == theArray[lastPos]){
                dpOfFirst[i] = dpOfFirst[i - 1] + 1;
            }
            else{ // the case like ABXABXA
                    // with dpOfFirst: 0001231
                int aux = lastPos;
                while(theArray[aux] != theArray[i] && aux != 0){
                    // you check the letters
                    aux = dpOfFirst[aux];
                }
                if(theArray[aux] == theArray[i]){
                    dpOfFirst[i] = dpOfFirst[aux] + 1;
                }
                else{
                    dpOfFirst[i] = 0;
                }
            }
        }
    }

}
vector<int> theResArray;
int main()
{
    fin.getline(theFirstArray, 2000001);
    fin.getline(theSecondArray, 2000001);
    int sizeOfFirstArray = strlen(theFirstArray);
    int sizeOfSecondArray = strlen(theSecondArray);
    preProcessing(theFirstArray, sizeOfFirstArray);
    int j = 0;
    int i = 0;
    // i - the index in the secondArray which you need to search in
    // j - the index in the firstArray which was pre-processed
    while(i < sizeOfSecondArray){

        if(theFirstArray[j] == theSecondArray[i]){
            ++j;
            ++i;
        }
        if( j == sizeOfFirstArray){
            theResArray.push_back(i - sizeOfFirstArray);
            j = dpOfFirst[j - 1];
            // so that you don't always start at 0
        }
        if (i < sizeOfSecondArray&& theFirstArray[j] != theSecondArray[i]){
             if(j != 0)
                    j = dpOfFirst[j - 1];
             else
                    i = i + 1;
        }
    }
    fout<<theResArray.size()<<'\n';
    for(int i = 0; i < theResArray.size(); i++){
        fout<<theResArray[i]<<" ";
    }
    return 0;
}