Cod sursa(job #2531083)

Utilizator Rares31100Popa Rares Rares31100 Data 25 ianuarie 2020 17:29:47
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 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
        {
            if(i)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
        {
            if(j)j=pat[j-1];
            if(cuv[j]==sir[i])
                j++;
        }

    out<<t<<'\n';

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

    return 0;
}