Cod sursa(job #2480798)

Utilizator victorv88Veltan Victor victorv88 Data 26 octombrie 2019 10:23:27
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int marime = 2000005;

int prefix[marime], l1,l2, re;

vector<int>rez;

char a[marime], b[marime], c;

void create_prefix()
{
    int poz;
    prefix[1]=0;
    for (int i=2; i<l1; ++i)
    {
        poz=prefix[i-1];
        while (poz!=0)
        {
            if (a[i]==a[poz+1])
            {
                prefix[i]=poz+1;
                break;
            }
            poz=prefix[poz];
        }
        if (poz==0)
        {
            if (a[1]==a[i])
                prefix[i]=1;
            else
                prefix[i]=0;
        }
    }
}

void solve()
{
    int ind=1;
    for (int i=1; i<l2; ++i)
    {
        if (b[i]==a[ind])
        {
            ind++;
            if (ind==l1)
            {
                ind=prefix[l1-1]+1;
                rez.push_back(i-l1+1);
            }
        }
        else
        {
            ind--;
            while (b[i]!=a[ind+1] && ind>0)
            {
                ind=prefix[ind];
            }
            if (a[ind+1]==b[i])
                ind+=2;
            else
                ind=1;
        }
    }
    int marime=min(1000,rez.size());
    g << rez.size() << '\n';
    for (int ind=0; ind<marime; ++ind)
    {
        g << rez[ind] <<' ';
    }
}

///ABA
///CABBCABABAB

int main()
{
    l1=1;
    l2=1;
    f >> a+1;
    f >> b+1;
    l1=strlen(a+1)+1;
    l2=strlen(b+1)+1;
    create_prefix();
    solve();
    return 0;
}