Как посчитать, сколько раз строка появляется в другой строке?

Мне нужно узнать, например, сколько раз test появляется в ttest, и ответ для этого будет 2, или, например, world в w1o1r1l1d и ответ будет один. Я уже написал код, который находит все возможности, а затем проверяет, является ли это строкой, которую я ищу, но это слишком медленно.


c++ string substring algorithm infix-notation
person Luka    schedule 12.04.2014    source источник
comment
Вы проверили что-нибудь из этого? en.wikipedia.org/wiki/String_searching_algorithm   -  person Ashalynd    schedule 13.04.2014
comment
Не могли бы вы поделиться своим кодом и как вы определили, что он слишком медленный.   -  person Mantosh Kumar    schedule 13.04.2014
comment
Не видя вашего кода, никто не подскажет, как его улучшить...   -  person πάντα ῥεῖ    schedule 13.04.2014
comment
Какой язык вы выбрали для реализации этого.   -  person Mantosh Kumar    schedule 13.04.2014
comment
stackoverflow.com/ вопросов/23032730/ вот мой полный код на паскале, но мне никто не помог :\   -  person Luka    schedule 13.04.2014
comment
То, что никто не ответил на ваш вопрос в первый раз, не означает, что вы должны публиковать его снова.   -  person Luigi    schedule 13.04.2014
comment
Поиск индекса первого вхождения строки, затем возобновление с индексом + длина строки до следующего вхождения и так далее до конца, пока идет подсчет.   -  person dtech    schedule 13.04.2014

Ответы (1)


arrow_upward
1
arrow_downward

Я бы попробовал рекурсивное решение.

Количество раз, когда строка из одной буквы появляется в другой строке, равно количеству раз, когда в ней появляются символы.

the number of time "r" appears in "program" is 2

Количество раз, когда строка из n букв появляется в другой строке, составляет:
количество раз, когда (n-1)- строка появляется после первого совпадения для первой буквы, плюс количество раз, когда строка из n букв появляется после первого матча

the number of times "test" appears in "ttest" is
      the number of times "est" appears in "test"
    + the number of times "test" appears in "test"

#include <stdio.h>
#include <string.h>

int count(const char *needle, const char *stack) {
  int n = 0;
  const char *p;
  if (*stack == 0) return 0;
  if (*needle == 0) return 0;
  p = strchr(stack, *needle);
  if (needle[1] == 0) n += !!p;
  if (p) {
    n += count(needle + 1, p + 1);
    n += count(needle, p + 1);
  }
  return n;
}

int main(void) {
  const char *needle, *stack;

  needle = "a"; stack = "";
  printf("[%s] exists %d times in [%s]\n", needle, count(needle, stack), stack);

  needle = ""; stack = "a";
  printf("[%s] exists %d times in [%s]\n", needle, count(needle, stack), stack);

  needle = "a"; stack = "abracadabra";
  printf("[%s] exists %d times in [%s]\n", needle, count(needle, stack), stack);

  needle = "br"; stack = "abracadabra";
  printf("[%s] exists %d times in [%s]\n", needle, count(needle, stack), stack);

  needle = "test"; stack = "ttest";
  printf("[%s] exists %d times in [%s]\n", needle, count(needle, stack), stack);

  needle = "world"; stack = "w1o1r1l1d";
  printf("[%s] exists %d times in [%s]\n", needle, count(needle, stack), stack);

  return 0;
}
person pmg    schedule 12.04.2014
comment
Вы можете увидеть работающий код на codepad.org: codepad.org/Jktgdbp7 - person pmg; 13.04.2014