KAN13C - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Dr. M Sohel Rahman
Tester: Jingbo Shang
Editorialist: Jingbo Shang

DIFFICULTY:

Medium

PREREQUISITES:

KMP

PROBLEM:

Given a string S[1…n], for each prefix of S[1…i], calculate largest pre[i], such that S[1…pre[i]] is same as S[i-pre[i]+1,i].

EXPLANATION:

This is a classical problem in Knuth–Morris–Pratt (KMP) algorithm.
It is easy to see that pre[i]≤pre[i-1]+1, since S[1…pre[i]]=S[i-pre[i]+1…i] and S[1…pre[i-1]]=S[i-pre[i-1]…i-1].
Furthermore, we can “Jump” followed the pre[]. Therefore, we can get the main procedure as following:

    pre[1] = 0;  // by the definition of the problem
    for (int i = 2; i <= n; ++ i) {
        int k = pre[i - 1];
        while (k != 0 && s[k + 1] != s[i]) {
            k = pre[k];
        }
        if (s[k + 1] == s[i]) {
            pre[i] = k + 1;
        } else {
            pre[i] = 0; // all failed
        }
    }

See Wiki Pedia for more details:

    http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2

Can u explain why this code is giving WA
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
char *str = (char *) malloc(4 * 1000000 * sizeof(char));
int *asv = (int *) malloc(4 * 1000000 * sizeof(int));
long long int i;
long long int j;
long long int k;
long long int l;

while (1) {
       scanf("%s", str);

       if (strcmp(str,"End") == 0)
            break;

       k = strlen(str);

       l = 0;

       for (i = 1; i < k; ++i) {
           if (str[i] == str[0])
               asv[i] = 1;
            else
                asv[i] = 0;
       }

       for (i = 1; i < k; ++i) {
             if (asv[i-1] >= 1 && asv[i-1] <= 9) {
                j = asv[i-1];
                if (str[i] == str[j]) {
                   asv[i] = j + 1;
                }
             }
        }

       for (i = 0; i < k; ++i)
           printf("%d ", asv[i]);

       printf("\n");

}

free(asv);
free(str);
return 0;

}
It is working fine for all cases in my system.
Ideone link is :-- http://ideone.com/vV6bYl
Thnx in advance