Cod sursa(job #2170531)

Utilizator PredaBossPreda Andrei PredaBoss Data 15 martie 2018 06:39:44
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
vector<int>identic,ap;
int counter;
void strmatch()
{
    int poz=0,inc=0,fid=0;
    while(poz<b.size())
    {
        bool k=1;
        while(fid<a.size() && poz<b.size() && a[fid]==b[poz])
        {
            fid++;
            k=0;
            poz++;
        }
        if(fid==a.size())
        {
            counter++;
            ap.push_back(inc);
            fid=identic[fid-1];
            inc=poz-fid;
            continue;

        }
        if(fid>0)
            fid=identic[fid-1];
        if(k)
        {
                inc=poz-fid+1;
                poz=inc+fid;
        }
        else
            inc=poz-fid;
    }
    fout<<counter<<"\n";
    if(counter<1000)
    for(int i=0;i<counter;i++)
        fout<<ap[i]<<" ";
    else
        for(int i=0;i<1000;i++)
        fout<<ap[i]<<" ";

}
int main()
{
    fin>>a>>b;
    identic.push_back(0);
    for(int i=1;i<a.size();i++)
    {
        if(a[identic[i-1]]==a[i])
        {
            identic.push_back(identic[i-1]+1);
            continue;
        }
        int j=identic[i-1];
        string secventa1,secventa2;
        secventa1.append(a,i-j+1,j);
        secventa2.append(a,0,j);
        while(j>1 && secventa1!=secventa2)
        {
            j--;
            secventa1.erase(i-j);
            secventa2.erase(j);
        }
        if(secventa1==secventa2)
            identic.push_back(j);
        else
            identic.push_back(0);
    }
    strmatch();
    return 0;
}