Cod sursa(job #1655317)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 17 martie 2016 21:44:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define LIM 1000

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int nr = 0;
const int NMAX = 2000001;
queue<int> coada;
char a[NMAX],b[NMAX];
int pi[NMAX];
int n,m;

void build_table()
{
    pi[1] = 0;
    int k = 0;
    for(int i=2;i<=n;i++)
    {
        while(k > 0 && a[k+1]!=a[i])
         k = pi[k];
        if(a[k+1]==a[i])
            k++;
        pi[i] = k;
    }
}

int main()
{
    in>>a>>b;
    n = strlen(a);
    m = strlen(b);
    for(int i = n;i>0;i--) a[i] = a[i-1];
    for(int i = m;i>0;i--) b[i] = b[i-1];
    build_table();
    ///
    int q = 0;
    for(int i=1;i<=m;i++)
    {
        while(q > 0 && a[q+1]!=b[i])
            q = pi[q];
        if(a[q+1]==b[i])
            q++;
        if(q==n)
        {
            nr++;
            if(nr<=LIM)
                coada.push(i-q);
            q = pi[q];
        }
    }
    out<<nr<<"\n";
    while(!coada.empty())
    {
        out<<coada.front()<<" ";
        coada.pop();
    }
    out.close();
    return 0;
}