Cod sursa(job #3150658)

Utilizator GrigMihaiGrigore Mihai GrigMihai Data 17 septembrie 2023 20:41:03
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
using namespace std;

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

char s[2000001], pattern[2000001];
int aux[2000001];

void buildaux()
{
    int i=1, j=0;
    aux[0]=0;

    while(pattern[i]!=0)
    {
        if(pattern[i]==pattern[j])
        {
            aux[i]=j+1;
            j++;
            i++;
        }
        else
        {
            if(j==0)
            {
                aux[i]=0;
                i++;
            }
            else
                j=aux[j-1];
        }
    }
}

int main() {

    in.getline(pattern, 2000000);
    in.getline(s, 2000000);

    buildaux();

    int i=0, j=0;
    vector<int> sols;
    while(s[i]!=0)
    {
        if(s[i]==pattern[j])
        {
            i++;
            j++;
            if(pattern[j]==0)
            {
                sols.push_back(i-j);
                j=aux[j-1];
            }
        }
        else
        {
            if(j==0)
                i++;
            else
                j=aux[j-1];
        }
    }

    out<<sols.size()<<'\n';
    for(int i=0;i<min(1000ull, sols.size());i++)
        out<<sols[i]<<" ";

    return 0;
}