Cod sursa(job #1306679)

Utilizator refugiatBoni Daniel Stefan refugiat Data 31 decembrie 2014 13:23:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int main()
{
    ifstream si;
    si.open("strmatch.in");
    ofstream so;
    so.open("strmatch.out");
    string a,b;
    si>>a>>b;
    int m=a.length();
    int v[m];
    int i;
    int l=0;
    v[0]=0;
    for(i=1;i<m;)
    {
        if(a[i]==a[l])
        {
            ++l;
            v[i]=l;
            ++i;
        }
        else
        {
            if(l>0)
            {
                l=v[l-1];
            }
            else
            {
                v[i]=0;
                ++i;
            }
        }
    }
    int sol=0,p[1002];
    int n=b.size();
    l=0;
    for(i=0;i<n;)
    {
        if(b[i]==a[l])
        {
            ++i;
            ++l;
        }
        if(l==m)
        {
            if(sol<1000)
                p[sol]=i-m;
            ++sol;
            l=v[l-1];
        }
        else
            if(i<n&&b[i]!=a[l])
            {
                if(l!=0)
                    l=v[l-1];
                else
                    ++i;
            }
    }
    so<<sol<<'\n';
    if(sol>1000)
        sol=1000;
    for(i=0;i<sol;++i)
        so<<p[i]<<' ';
    so<<'\n';
}