Cod sursa(job #2531108)

Utilizator Rares31100Popa Rares Rares31100 Data 25 ianuarie 2020 18:05:04
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

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

string cuv,sir;
int pat[2000000];
int sol[1001],t;

void createSuffix()
{
    int i=0,j=1;

    while(j<cuv.size())
    {
        if(cuv[i]==cuv[j])
        {
            pat[j]=i+1;
            i++;
            j++;
        }
        else
        {
            while(i && cuv[i]!=cuv[j])
                i=pat[i-1];

            if(cuv[i]==cuv[j])
                continue;
            else
                j++;
        }
    }
}

int main()
{
    in>>cuv>>sir;

    createSuffix();

    int j=0;
    for(int i=0;i<sir.size();i++)
        if(cuv[j]==sir[i])
        {
            j++;
            if(j==cuv.size())
            {
                j=pat[j-1];
                t++;
                if(t<=1000)
                    sol[t]=i-cuv.size()+1;
            }
        }
        else
        {
            while(j && cuv[j]!=sir[i])
                j=pat[j];
            if(cuv[j]==sir[i])
                j++;
        }

    out<<t<<'\n';

    for(int i=1;i<=t;i++)
        out<<sol[i]<<' ';

    return 0;
}