Cod sursa(job #2000697)

Utilizator mirunafrancescaMiruna mirunafrancesca Data 14 iulie 2017 14:05:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

#define NMAX 2000000
char a[NMAX], b[NMAX];
int v[1000], lps[NMAX], s[NMAX];

///algoritmul kmp

void ps()
{
    int i=1, len=0;
    lps[0]=0;
    while(i<strlen(a))
    {
        if(a[i]==a[len])
        {   len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if(len==0)
              {
                  i++;
                  lps[i]=0;
              }
            else
            {
                len=lps[len-1];
            }
        }
    }
}

void kmp(int &nr)
{
    int i, j;
    i=j=0;
    while(i<strlen(b))
    {
        if(a[j]==b[i])
        {
            i++;
            j++;
            if(j==strlen(a))
             {
                 nr++;
                 s[nr]=i-j;
                 j=lps[j-1];
             }
        }
       else
        {
            if(j!=0)
                j=lps[j-1];
            else
                i++;
        }
    }
}
int main()
{   freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin.getline(a,2000000);
    cin.getline(b,2000000);

    /*char *p;
    int nr=0, i=0;
    p=strstr(b,a);
    while(p)
    {
        i++;
        v[i]=p-b;
        nr++;
        p++;
        p=strstr(p,a);
    }
    cout<<nr<<endl;

    if(i>0)
    for(int j=1; j<=1000 && j<=i; j++)
        cout<<v[j]<<" ";
    cout<<endl;*/

    ps();
    int nr=0;
    ps();
    kmp(nr);
    cout<<nr<<endl;
    for(int i=1; i<=nr; i++)
        cout<<s[i]<<" ";
    return 0;
}