Cod sursa(job #1830920)

Utilizator GrasuneAlexandruGrasune Alexandru Mihai GrasuneAlexandru Data 17 decembrie 2016 11:35:26
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;
string text,patern;
int sir[20000000],nr=0,x=0,a[100];
void citire()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    getline(cin,patern);
    getline(cin,text);


}
void patern_making()
{

    int n=patern.length();
    int j=0;
    for(int i=1; i<n; i++)
    {
        if(patern[i]==patern[j])
        {
            sir[i]=j+1;
            j++;
        }
        else

        {
            j--;

            while(j>=0)
            {
                j=sir[j];
                if(patern[i]==patern[j])
                {
                    sir[i]=j+1;

                    j++;
                    break;
                }
                else
                    j--;



            }
            if(j<0)
            {
                sir[i]=0;
                j=0;
            }

        }
    }
}
void cautare()
{
    int j=0,v=0;
    int n=patern.length();
    int m = text.length();
    for(int i=0; i<m; i++)
    {
        if(text[i]==patern[j])
            j++;
        else if(j)
            j=sir[j-1];
        if(j==n)
        {
            nr++;
            j = sir[j - 1];
            a[x++]=i-n+1;

        }
    }
}

int main()
{
    citire();
    patern_making();
    cautare();
    int n=patern.length();
    cout<<nr<<endl;
    for(int i=0;i<x;i++)
        cout<<a[i]<<" ";



    return 0;
}