Cod sursa(job #1648987)

Utilizator jordasIordache Andrei Alexandru jordas Data 11 martie 2016 12:12:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <cstring>
#include <list>

using namespace std;

 ifstream x ("strmatch.in");
 ofstream y ("strmatch.out");

 int nr_rez;
 int n,m;
 int table[2000000];
 char text[2000000];
 char word[2000000];

 list<int> l;

 void create_table()
 {
     int i;
     int cnd=0;

     table[0]=-1;
     table[1]=0;

     for(i=2;i<m;i++)
        if(word[i-1]==word[cnd])
        {
            table[i]=cnd+1;
            cnd+=1;
        }
        else
            if(cnd>0)
                cnd=table[cnd];
            else
                table[i]=0;
 }

 void kmp(int i)
 {
     int j=0;

     while(i+m<=n)
        if(word[j]==text[i+j])
        {
            if(j==m-1)
            {
                nr_rez++;
                l.push_back(i);
                //y<<i<<' ';
                kmp(i+1);
                break;
            }
            j++;
        }
        else
           if(table[j]>-1)
           {
               i=i+j-table[j];
               j=table[j];
           }
           else
           {
               i++;
               //j=0;
           }
 }

int main()
{
    int i;

    x>>word;
    x>>text;

    n=strlen(text);
    m=strlen(word);

    create_table();
/*
    for(i=0;i<m;i++)
        y<<table[i]<<' ';
    y<<'\n';
*/
    kmp(0);

    y<<nr_rez<<'\n';

    while(!l.empty())
    {
        y<<l.front()<<' ';
        l.pop_front();
    }
    y<<'\n';

    return 0;
}