Lcp - Эффективно подсчитать количество различных подстрок в строке

@Весбат · Регистрация: 11.12.2014

Author24 — интернет-сервис помощи студентам

Строить научился. Как с помощью его анализа эффективно подсчитать количество различных подстрок в строке, которые встречаются 2 или более числа раз. Строки могут перекрываться.
Строки в нижнем регистре из англ. букв.

К примеру:
ababcabb - 3 строки (a, b, ab)
mississippi - 9 строк

Байт · 07.06.2016, 08:17

Как-то так.

C

int cmp(char *s1, char *s2, int n)
{ int i;
   for(i=0; i<n; i++)
     if (s1[i] !=s2[i]) return 0;
   return 1;
}
int main()
{ char *str = "mississippi";
   char *p;
   int N = 0, i, j;
   for (p=str; *(p+1)!= '\0'; p++) {
      for(i=1; i<=strlen(p); i++) {
         for(j=0; j<strlen(str); j++) {
            if (j = p - str) continue;
            if (cmp(p, str+j, i)) {
               if (j < p - str) break; // подстрока уже подсчитана
               N++;
               printf("%-*.*s\n", i, i, p);
               break;  // Дальнейшие повторы можно не проверять
            }
         } 
      } 
   }
   printf("N=%d\n", N);
}

Псевдокод. Не проверял.
Возможна оптимизация.

@Весбат 0 / 0 / 0 Регистрация: 11.12.2014 Сообщений: 4
		1
	Lcp - Эффективно подсчитать количество различных подстрок в строке 07.06.2016, 01:35. Показов 2464. Ответов 1 Метки нет (Все метки) Строить научился. Как с помощью его анализа эффективно подсчитать количество различных подстрок в строке, которые встречаются 2 или более числа раз. Строки могут перекрываться. Строки в нижнем регистре из англ. букв. К примеру: ababcabb - 3 строки (a, b, ab) mississippi - 9 строк 0

	07.06.2016, 08:17

Lcp - Эффективно подсчитать количество различных подстрок в строке

Решение