Cod sursa(job #2557679)

Utilizator victorv88Veltan Victor victorv88 Data 25 februarie 2020 22:21:41
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int>rez;
int pattern[200005];
int l;
char sir1[2000005], sir2[200005];

void create_pattern()
{
    int j=1, i=0;
    while(j<l)
    {
        if (sir1[i]==sir1[j])
        {
            pattern[j]=pattern[j-1]+1;
            i++;
        }
        else
        {
            while(i!=0)
            {
                if(sir1[i]==sir1[j])
                {
                    pattern[j]=i+1;
                    i++;
                    break;
                }
                else
                    i=pattern[i-1];
            }
            if(sir1[0]==sir1[j])
                pattern[j]=1;
            else
                pattern[j]=0;
        }
        ++j;
    }
}

void parcurgere()
{
    int l2=strlen(sir2);
    int ind_pattern=0;
    for (int i=0; i<l2; ++i)
    {
        if(sir2[i]==sir1[ind_pattern])
        {
            ++ind_pattern;
            if(ind_pattern==l)
            {
                rez.push_back(i-l+1);
                ind_pattern=pattern[ind_pattern-1];
            }
        }
        else
            ind_pattern=pattern[ind_pattern];
    }
}

int main()
{
    f >> sir1 >> sir2;
    l=strlen(sir1);
    create_pattern();
    parcurgere();
    g << rez.size()<<'\n';
    for (auto &v:rez)
        g << v <<' ';
    return 0;
}