Cod sursa(job #1301827)

Utilizator jordasIordache Andrei Alexandru jordas Data 26 decembrie 2014 13:54:56
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>

using namespace std;

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

 int size[20];
 int v[1000000];
 char pattern[2000000];
 char text[2000000];

int main()
{
    int i,j;
    int n,m;

    x>>pattern;
    x>>text;

    n=strlen(pattern);

    for(i=1;i<n;i++)
       if(size[i-1] && pattern[i]==pattern[size[i-1]])
          size[i]=size[i-1]+1;
       else
          if(pattern[i]==pattern[0])
             size[i]=1;
/*
    for(i=0;i<n;i++)
       y<<size[i]<<' ';
    y<<'\n';
*/
    m=strlen(text);

    bool flag;
    int k=0;

    for(i=0;i<m-n;i++)
    {
        flag=true;

        for(j=0;j<n;j++)
           if(text[i+j]!=pattern[j])
           {
               flag=false;
               i+=size[j-1];
               break;
           }

        if(flag==true)
        {
            k++;
            v[k]=i;
        }
    }

    y<<k<<'\n';
    for(i=1;i<=k;i++)
       y<<v[i]<<' ';
    y<<'\n';

    return 0;
}