Cod sursa(job #1360899)

Utilizator jordasIordache Andrei Alexandru jordas Data 25 februarie 2015 18:39:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <cstring>
#define nMax 2000000

using namespace std;

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

 char key[nMax],code[nMax];
 int PMT[nMax];
 int poz[100005];

 void generate_PMT(int n)
 {
     int i;

     for(i=1;i<n;i++)
        if(key[i]==key[PMT[i-1]])
           PMT[i]=PMT[i-1]+1;
        else
           if(key[i]==key[0])
              PMT[i]=1;
/*
     y<<key;
     y<<'\n';

     for(i=0;i<n;i++)
        y<<PMT[i];
     y<<'\n';
*/
 }

int main()
{
    int i;

    x>>key;
    x>>code;

    generate_PMT(strlen(key));

    bool match;
    int n=strlen(key);
    int N=strlen(code);
    int j,k=-1;

    for(i=0;i<N-n+1;i++)
    {
        j=0;
        match=false;

        while(code[i+j]==key[j] && j<n)
        {
            j++;
            match=true;

            if(j==n)
            {
                k++;
                poz[k]=i;
            }
        }

        if(match==true)
           i+=j-PMT[j-1]-1;
    }

    y<<k+1<<'\n';

    if(k>999)
       k=999;

    for(i=0;i<=k;i++)
       y<<poz[i]<<' ';
    y<<'\n';

    return 0;
}