Cod sursa(job #1792123)

Utilizator mariakKapros Maria mariak Data 30 octombrie 2016 01:02:02
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define Dim 2000002
#define Lim 1002
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

using namespace std;
char pattern[Dim], text[Dim], sol[Lim];
int F[Dim], n, m;
void internal_rules()
{
    int j;
    F[0] = F[1] = 0;
    for(int i = 2; i <= n; ++ i)
    {
        j = F[i - 1];
        for( ; ; )
        {
           /// check to see if the last ch of string(prefix) i
           ///  expands the current candidate
           if(pattern[i - 1] == pattern[j])
           {
               F[i] = j + 1;
               break;
           }
           if(j == 0)
           {
               F[i] = 0;
               break;
           }
           j = F[j];
        }
    }
}
void KMP()
{
    int i = 0, j = 0;
    internal_rules();
    for( ; ; )
    {
        if(j == m) break;
        /// if the current ch of the text
        /// expands the current match
        if(text[j] == pattern[i])
        {
            ++ i; /// change current state of automaton
            ++ j; /// next character
            if(i == n && sol[0] < Lim)
                sol[++ sol[0]] = j - n;
            if(sol[0] == Lim) return;
        }
        else if(i > 0) i = F[i];
        else ++ j;
    }
}
void write()
{
    printf("%d\n", sol[0]);
    for(int i = 1; i <= sol[0]; ++ i)
        printf("%d ", sol[i]);
}
int main()
{
    gets(pattern);
    n = strlen(pattern);
    gets(text);
    m = strlen(text);
    KMP();
    write();
    return 0;
}