ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1423. Басня о строке

Why Runtime error (access violation) ?
Послано Kimbizin 4 июн 2014 22:18
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_READ 250000
#define MASIVE(a, b) (b *) malloc(sizeof(b *)*(a))
#define STRING(a) MASIVE((a), char);

#define R_CONCAT(T,S,A) strcat(A, T); \
                        strcat(A, " "); \
                        strcat(A, S); \

int * Z_simple(char * str, int len) {
  int * z = MASIVE(len, int);

  for (int i = 1;  i < len; i++) {
    int * val = z + i;
    *val = 0;
    for (int j = 0; i + j < len; j++) {
      if (str[i + j] != str[j]) {
        break;
      }
      (*val)++;
    }
  }
  return z;
}

int * Z(char * str, int len) {
  int * z = MASIVE(len, int);
  int l = 0, r = 0;

  for (int k = 1; k < len; k++) {
    if (k > r) {
      l = k;
      int pos = 0;

      while (k + pos < len && str[pos] == str[k + pos]) {
        pos++;
      }

      if (pos == 0) {
        r = l;
        z[k] = 0;
      } else {
        r = k + pos - 1;
        z[k] = pos;
      }

    } else {
      int m = k - l;
      int b = z[l] - m;
      if (z[m] < b) {
        z[k] = z[m];
      } else {

        int pos1 = b;
        int pos2 = k + b;
        int pos = 0;

        while(pos2 + pos < len && str[pos1 + pos] == str[pos2+pos]) {
          pos ++;
        }

        if (pos != 0) {
          l = k;
          r = pos2 + pos - 1;
          z[k] = b + pos;
        } else {
          z[k] = b;
        }

      }
    }

  }

  return z;
}



int main() {

    int n;
    int result = -1;
    scanf("%d", &n);

    char * T = STRING(n);
    char * S = STRING(n);

    scanf("%s%s", T, S);

    int len_N = 2*n + 1;

    char * N = STRING(len_N);

    R_CONCAT(T,S,N);

    int * z = Z(N, len_N);
    z = z + (n + 1);

    for (int i = 0; i < n; i++) {
        if (z[i] == n - i) {
            int k = z[i];
            int b = 0;
            for (int j = 0; j < i; j++) {
                if (T[k + j] != S[j]) {
                     b = 1;
                     break;
                }
            }
            if (b == 0)
                result = i;
            break;
        }
    }

    printf("%d", result);
}