Cod sursa(job #1279862)

Utilizator LegionHagiu Stefan Legion Data 30 noiembrie 2014 23:42:30
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
string a,b;
int tbl[2000001];
vector<int> solutii;
void potrivire()
{
    tbl[0]=-1;
    int k=-1,i;
    for (i=1;i<a.size();i++)
    {
        if (a[k+1]==a[i])
        {
            k++;
        }
        else while (k>-1&&a[k]!=a[i])
        {
            k=tbl[k];
        }
        tbl[i]=k;
    }
}
void rezolvare()
{
    int i,k=0;
    for (i=0;i<b.size();i++)
    {
        while(k>=0&&a[k+1]!=b[i])
        {
            k=tbl[k];
        }
        if (a[k+1]==b[i])
        {
            k++;
        }
        if (k==a.size()-1){solutii.push_back(i-k);}
    }
}
void afisare()
{
    ofstream out("strnatch.out");
    int i;
    out<<solutii.size();
    out<<"\n";
    for (i=0;i<solutii.size();i++)
    {
        out<<solutii[i]<<" ";
    }
}
int main()
{
    ifstream in("strmatch.in");
    in>>a;
    in>>b;
    potrivire();
    rezolvare();
    afisare();
}