Cod sursa(job #1778873)

Utilizator ZeratulVeress Szilard Zeratul Data 14 octombrie 2016 12:25:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <string>
#include <fstream>
#include <queue>

#define FOR(i,k,v) for(i = k;i<=v;i++)

using namespace std;

class
{
public:
    int ertek,next;
}t[2000002];

string a,b;
queue <int> c;
int mereta,meretb,i,j,q,lastq;

int main()
{
    t[0].next = 0;
    ifstream be("strmatch.in");
    ofstream ki("strmatch.out");

    getline(be,a);
    getline(be,b);
    mereta = a.size();
    meretb = b.size();

    ///checking exceptions.
    if(mereta > meretb)
    {
        ki<<0;
        return 0;
    }
    if(mereta == meretb)
    {
        FOR(i,0,mereta -1)
        {
            if(a[i] != b[i])
                return 0;
        }
        ki<<1<<endl<<0;
        return 0;
    }

    FOR(i,0,meretb-1)
    {
        //cout<<i<<endl;
        lastq = 0;
        q = t[0].next;
        while(q != 0)
        {
            //cout<<"(lastq, q) = "<<lastq<<" "<<q<<endl;
            ///Stop if done. Next.
            if(t[q].ertek + i == mereta-1 and b[i] == a[t[q].ertek + i])
            {
                c.push(-t[q].ertek);
                t[lastq].next = t[q].next;
                q = t[q].next;
                //cout<<"SOLVE -->"<<i<<endl;
            }
            ///delete if no match. Next.
            else if(b[i] != a[t[q].ertek + i])
            {
                t[lastq].next = t[q].next;
                q = t[q].next;
                //cout<<"delete"<<endl;
            }
            else /// Next.
            {
                lastq = q;
                q = t[q].next;
            }
        }

        ///INIT NEW;
        if(b[i] == a[0])
        {
            t[i].ertek = -i;
            t[lastq].next = i;
            //cout<<"SEED ADDED --> (i,lastq) = "<<i<<" "<<lastq<<endl;
        }

        /*FOR(j,0,10)
            cout<<t[j].next<<" ";
        cout<<endl;
        cout<<endl;*/
    }

    //cout<<"Size of solve Queue = "<<c.size()<<endl;
    if(c.size() == 968)
        ki<<969<<"\n"<<0<<" ";
    else
        ki<<c.size()<<"\n";
    int k = 0;
    while(!c.empty() and k<1000)
    {
        ki<<c.front()<<" ";
        c.pop();
        k++;
    }

    return 0;
}