Cod sursa(job #2891108)

Utilizator DMR6476Erdic Dragos DMR6476 Data 17 aprilie 2022 15:57:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.04 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;
                }
            }
        }
    }

}
void sol(vector<int> &theResArray, int sizeOfFirstArray, int sizeOfSecondArray, int &sizeOfRes)
{
    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)
        {
            if(sizeOfRes < 1000)
            {
                theResArray.push_back(i - sizeOfFirstArray);
                ++sizeOfRes;
            }
            else
                ++sizeOfRes;
            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;
        }
    }
}

int main()
{
    vector<int> theResArray;
    fin.getline(theFirstArray, 2000001);
    fin.getline(theSecondArray, 2000001);
    int sizeOfFirstArray = strlen(theFirstArray);
    int sizeOfSecondArray = strlen(theSecondArray);
    preProcessing(theFirstArray, sizeOfFirstArray);
    int sizeOfRes = 0;
    sol(theResArray, sizeOfFirstArray, sizeOfSecondArray,sizeOfRes);
    fout<<sizeOfRes<<'\n';
    for(int i = 0; i < min(sizeOfRes , 1000); i++)
    {
        fout<<theResArray[i]<<" ";
    }
    return 0;
}