подсчет вхождения подстрок

Question

Есть ли эффективный алгоритм для подсчета общего количества вхождений подстроки X в более длинную строку Y?

Чтобы быть более конкретным, что я хочу есть, общее количество способов выбора a.size() элементов из В, что существует перестановка выбранных элементов, что матчи B.

Примером может служить следующим образом: найдите общее число находок X=AB в строке Y=ABCDBFGHIJ?

Ответ 2: первый А и второй В, и первый А и 5-й Б.

Я знаю, что мы можем создать все перестановки длинной строки (которая будет N! длина строки NY) и используйте алгоритм KMP для поиска/подсчета вхождения X в Y.

Можем ли мы сделать это лучше?

Исходная проблема, которую я пытаюсь решить, заключается в следующем: допустим, у нас есть большая матрица M размера r на c (r и c в диапазоне 10000). Учитывая малую матрицу P размера a на b (a и b находятся в диапазоне 10). Найдите общее количество различных выборок строк и b столбцов M (это даст нам подмногочку «a» b »), так что существует перестановка строк и столбцов матрицы H, которая дает нам матрицу, которая соответствует P .

Я думаю, что как только я смогу решить одномерный случай, 2-D может следовать за решением.

После исследования выясняется, что это проблема изоморфизма подграфа и NP-сложная. Некоторые алгоритмы эффективно решают эту задачу. Можно это сделать и посмотреть на это много статей.

Answer 1

После того, как вы прочитали, перечитайте вопрос (по предложению @Charlie), я пришел к выводу, что эти ответы не затрагивают реальную проблему. Я также пришел к выводу, что я до сих пор не знаю точно, в чем проблема, но если ответы на OP отвечают на мои вопросы и проясняют проблему, я вернусь и сделаю более эффективную попытку решить эту проблему. На данный момент, я оставлю это как держатель место ...

Для поиска вхождений буквы или другого характера:

char buf[]="this is the string to search"; 
int i, count=0, len; 
len = strlen(buf); 
for(i=0;i<len;i++) 
{ 
    if(buf[i] == 's') count++; 
}  

или, используя strtok(), найти вхождения подстроки:
Не красивый, грубый метод.
// строки для поиска

char str1[]="is"; 
char str2[]="s"; 
int count = 0; 
char buf[]="this is the string to search"; 
char *tok; 
tok = strtok(buf, str1); 
while(tok){ 
    count++; 
    tok = strtok(NULL, str1); 
} 
tok = strtok(buf, str2); 
while(tok){ 
    count++; 
    tok = strtok(NULL, str2); 
} 

количество должно содержать общее количество вхождений "с", + вхождения "является"

[EDIT]
Во-первых, позвольте мне спросить для технического уточнения вашего вопроса, учитывая A = «AR», B = «START», решениями будут «A», «R» и «AR», в этом случае все, найденные в 3-м и 4-м буквах B . Это верно?. Если так, это достаточно легко. Вы можете сделать это с небольшими изменениями и дополнениями к тому, что я уже сделал выше. И если у вас есть вопросы об этом коде, я был бы рад обратиться к ним, если смогу.

Вторая часть ваш реальный вопрос: Поиск с лучше или, по крайней мере, с той же эффективностью, что и KMP algorithm - это реальный трюк. Если выбор наилучшего подхода - это реальный вопрос, то некоторые поиски Google в порядке. Потому что, как только вы найдете и соглашаетесь на лучший подход (эффективность> = KPM) для решения поиска подстроки, тогда реализация будет набором простых шагов (if you give it enough time), возможно, но не обязательно с использованием некоторых из тех же компонентов используемого выше. (Манипуляция указателем будет быстрее, чем использование строковых функций, которые я думаю.) Но эти методы - это просто реализация и всегда должны следовать хорошему дизайну. Вот несколько Google поиск, чтобы помочь вам начать работу с поиском ... (Вы, возможно, уже в некоторых из них)

Validating KMP
KMP - Can we do better?
KMP - Defined
KMP - Improvements using Fibonacci String

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

Answer 2

Если X является подстрокой в ​​Y, то каждый символ X должен быть в Y. Поэтому сначала мы итерации по X и находим отсчеты каждого символа в массиве counts.

Затем для каждого символа, который имеет count >= 1, мы подсчитываем количество раз, которое оно отображается в Y, которое можно сделать тривиально в O(n).

Отсюда ответ должен быть просто умножением комбинаций C(count(Y),count(X)).

Если после третьего чтения вашего вопроса я, наконец, понял его правильно.