Cod sursa(job #671013)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 30 ianuarie 2012 16:05:59
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<assert.h>
#include<iostream>
#include<string>
#include<vector>

using namespace std;

string a,b;
int n,prefix[2001000];
vector <int> sol;

void read()
{
    assert(freopen("strmatch.in","r",stdin)!=NULL);
    cin >> a;
    cin >> b;
}

void get_prefix()
{
    prefix[0]=-1;
    int i,j=0;
    for(i=1;i<a.size();++i)
    {
        while(j!=-1)
        {
            if(a[i]==a[j])
            {
                prefix[i]=j;
                ++j;
                break;
            }
            j=prefix[i-1];
        }
        if(j==-1)
        {
            j=0;
            prefix[i]=-1;
        }
    }
}

void print_prefix()
{
    int i;
    for(i=0;i<a.size();++i)
        printf("%d ",prefix[i]);
}

void find_matches()
{
    int i,j=0;
    for(i=0;i<b.size();++i)
    {
        while(j!=-1)
        {
            if(a[j]==b[i])
            {
                if(j==a.size()-1)
                {
                    ++n;
                    if(n<=1000)
                        sol.push_back(i);
                    j=prefix[j]+1;
                }
                else
                {
                    ++j;
                }
                break;
            }
            j=prefix[j];
        }
        if(j==-1)
            j=0;
    }
}

void solve()
{
    get_prefix();
    //print_prefix();
    find_matches();
}

void write()
{
    assert(freopen("strmatch.out","w",stdout)!=NULL);
    int i;
    printf("%d\n",n);
    for(i=0;i<sol.size();++i)
        printf("%d ",sol[i]-a.size()+1);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}