Форум программистов, компьютерный форум CyberForum.ru

Поиск подстроки - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Переставить байты исходного файла в обратном порядке http://www.cyberforum.ru/cpp-beginners/thread1201120.html
7. По заданному двоичному файлу с произвольным содержанием создать новый двоичный файл, у которого байты переставлены в обратном порядке. Вывести содержимое исходного и итогового файлов на экран.
C++ Изменение значения указателя Здравствуйте В коде приведена функция, которая при помощи указателей считывает размер массива и его элементы из файла блокнота. Почему значение, хранящееся в массиве после выполнения цикла самопроизвольно меняется? функция мэйн #include <iostream> #include <stdlib.h> #include <windows.h> http://www.cyberforum.ru/cpp-beginners/thread1201114.html
C++ Рекурсивная функция, выводящая на экран все целые числа от N до K, N<K
рекурсивная функция, выводящая на экран все целые числа от N до K, N<K
C++ Написать рекурсивную функцию, выводящую на экран все целые числа в определенном интервале
рекурсивная функция, выводящая на экран все целые числа от N до K, N<K
C++ Можно ли обратиться к 3 элементу массива ? http://www.cyberforum.ru/cpp-beginners/thread1201086.html
Если у нас есть int *x, y = { 1,2,3,4,5 }, можно ли обратиться к 3 элементу массива вот так? x=y; *(x+2) Думаю, что нет, так как не взят адрес x=&y А что вобще произойдет при таком условии? x=y
C++ Перед указанным элементом массива вставить новый элемент Дан массив размера N и целое число K (1 ≤ K ≤ N). Перед элемен- том массива с порядковым номером K вставить новый элемент с нулевым значением. подробнее

Показать сообщение отдельно
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
06.06.2014, 19:35     Поиск подстроки
Сделайте так:

Для начала надо научиться считать префикс-функцию от строки
C++
1
2
3
4
5
6
7
8
9
vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=0; i<n; ++i)
        for (int k=0; k<=i; ++k)
            if (s.substr(0,k) == s.substr(i-k+1,k))
                pi[i] = k;
    return pi;
}
Затем делаем следующую строку
C++
1
s=a+'#'+b;
a-это то,ЧТО мы ищем
b-это то,В ЧЕМ мы ищем.
+ - конкатация
# - любой символ, которого нет ни в a, ни в b

Найдем префикс фунцию от этой строки.
Пусть длина a будет n, а b - m.
Тогда

C++
1
2
3
4
5
6
7
8
9
for(int i=n;i<n+m+1;i++)
    {
    if(pi[i]==n)
        {
        cout<<"YES"<<endl
        return 0;
        }
    }
    cout<<"NO"<<endl;
Добавлено через 19 секунд
pi - это вектор с префикс функии строки s
 
Текущее время: 12:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru