С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.60
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

Молниеносное нахождение подстрок - C++

25.08.2011, 20:21. Просмотров 2672. Ответов 43
Метки нет (Все метки)

Воодится число тестов. Далее каждый тест содержит 2 строки. Подстроку и текст. Надо найти количество подстрок в тексте. Количество тестов неизвестно, но много. Длина подстроки 10000, а текста 1000000.
Вот мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
string str1;
string str2;
string str;
int i,n,m,q=0,t,k,a;
int *mas;
cin >> t;
while (t--)
{
 cin >> str2;
 cin >> str1;  
 n=str1.length();
 m=str2.length();
 mas=(int*)malloc((n+m+1)*sizeof(int));
 str=str2+'#'+str1; mas[0]=0;
 a=0; k=0; q=0;
 for(i=1; i<n+m+1; i++)
  {         
   while((k>0) && (str[k]!=str[i])) k=mas[k-1];
   if (str[k]==str[i]) k++;
   if (k==m) q++;
   mas[i]=k;
  }
 cout << q << endl;
}
return 0;
}
Медленно, кто-нибудь может ускорить?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2011, 20:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Молниеносное нахождение подстрок (C++):

Поиск подстрок - C++
Задание подсчитать все подстроки с использованием функции strstr(). Делаю так: int NumSubStr(char *str1, char *str2){ int result...

Количество подстрок в строке - C++
Нужно что-бы пользователь ввел 2 строки и ему вывело сообщение о том, сколько раз встречается строка 2 в первой строке. Как это сделать без...

Удаление подстрок из строки - C++
Помогите, пожалуйста, с реализацией функции. Есть строка str типа string и строка it типа char. Нужно из str удалить все it. Например, ...

Подсчёт количества подстрок - C++
Посмотрите пожалуйста нормально ли написана функция, которая считает количество подстрок? int SearchSubString(char *s1,char *s2){ ...

Удаление всех подстрок из строки - C++
Здравствуйте. После выполнения моей программы у меня выдает вот такую ошибку #include &lt;iostream&gt; #include &lt;string&gt; ...

Подсчитать количество подстрок в текстовом файле - C++
Помогите написать программу которая может подсчитать сколько раз подстрока встречается в текстовом файле.

43
Сыроежка
Заблокирован
25.08.2011, 21:09 #16
Цитата Сообщение от diagon Посмотреть сообщение
Я тоже так думал =)
Вот
Вот код
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cstring>
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    char a[999999], b[999999], *p = a;
    std::cin.getline(a, 999999);
    std::cin.getline(b, 999999);
    for (; p = strstr(p, b) ; *p++ = 0)
        std::cout << p - a << ' ';
}
Не проходит по времени. КМП там же менее чем за 0.1 секунду справляется.
Наверное очевидно потому, что вместо вызовов функций используются встроенная функция.
0
-=ЮрА=-
Заблокирован
Автор FAQ
25.08.2011, 21:10 #17
Цитата Сообщение от AvengerAlive Посмотреть сообщение
mas=(int*)malloc((n+m+1)*sizeof(int));
- это не так делается, каждый раз память с нуля выделять
Алгоритм такой выделям память изначально malloc-ом, а затем изменяем её при помощи realloc, обрати внимание на вот эту строку моего топика
C++
1
bin = (char *)realloc(bin,(1 + (i = i + 1))*sizeof(char));
Сложение в двоичной системе счисления

Как пример конструкции malloc - realloc привожу проектик
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <windows.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
 
//Ввод до того как не введём символ окончания ввода, \n - нажмём Enter
char * get_text(char * s, char ch_end, int &sLen);
 
int main()
{
    int sLen = 0;
    char * str = (char *)malloc(sizeof(char));
    do
    {
        printf("\tEnter text\r\n");
        str = get_text(str, '\n', sLen);
        printf("\tYour input :\r\n%s\r\n",str);
        printf("[Y/N] Y - new input\r\n");
    }
    while(toupper(getch()) == 'Y');
    return 0;
}
 
char * get_text(char * s, char ch_end, int &sLen)
{
    sLen = 0;
    if(s)
    {
        while((s[sLen] = getchar()) != ch_end)
            s = (char *)realloc((void *)s,(1 + (sLen = sLen + 1))*sizeof(char));
        s[sLen] = '\0';//Избавляемся от мусора, вконце строки
    }
    return s;
}
0
Миниатюры
Молниеносное нахождение подстрок  
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:12  [ТС] #18
Сыроежка, Я говорю медленно работает моя прога с таким алгоритмом, а ты мне про find, который наивный. Существует сложность алгоримов, чем она меньше тем быстрее прога работает. Поэтому find не получается, с ним уже 5 тестов TL.


diagon, Задачка почти та, только надо количество вывести, а не каждый символ. Да и тестов там больше, и большие они.
0
Сыроежка
Заблокирован
25.08.2011, 21:13 #19
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Сыроежка, Я говорю медленно работает моя прога с таким алгоритмом, а ты мне про find, который наивный. Существует сложность алгоримов, чем она меньше тем быстрее прога работает. Поэтому find не получается, с ним уже 5 тестов TL.
До вас с первого раза не доходит? Ваша программа некорректная! Сколько еще раз повторять?!

Я вам уже сказал, что вам не о сложности надо рассуждать, а научиться писать элементарные конструкции на С++.
2
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:18  [ТС] #20
Сыроежка, чего там некорректного? Прошло 12 тестов из 15, да и ещё по причине TL, а так без TL прошло бы быстрее.
0
Сыроежка
Заблокирован
25.08.2011, 21:19 #21
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Сыроежка, чего там некорректного? Прошло 12 тестов из 15, да и ещё по причине TL, а так без TL прошло бы быстрее.
Я вам уже указывал, что там некорректного. Программа вообще какая-то бредовая! И ее поведение неопределенное.
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:26  [ТС] #22
Сыроежка, я у людей попросил ускорить программу, а не указывать на её ошибки. Там ошибок нету, работает она нормально. Это префикс-функция и её работа была доказана ещё давно.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.08.2011, 21:27 #23
Тут почитать можно.
http://e-maxx.ru/algo/prefix_function
0
Сыроежка
Заблокирован
25.08.2011, 21:28 #24
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Сыроежка, я у людей попросил ускорить программу, а не указывать на её ошибки. Там ошибок нету, работает она нормально. Это префикс-функция и её работа была доказана ещё давно.
Как можно ускорить какой-то бред?! Ускорить можно лишь то, что корректно написано. А когда человек сам не понимает, что делает его программа, а тем более и другие не понимают, глядя на этот написанный бред, то что ускорять-то будем?!

И я не вижу никакой "префикс-функции". Я вижу цикл while, который ни разу не исполняется.
0
ValeryLaptev
Эксперт С++
1046 / 825 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
25.08.2011, 21:33 #25
AvengerAlive, попробуйте алгоритм Рабина-Карпа.
Суть его в том, что вычисляется хеш-значение по искомому слову.
Далее бежим по строке поиска и ищем первый символ искомой строки в строке поиска. Если символ обнаружен - считаем хеш-значение подстроки в строке поиска. Если совпало - только тогда проверяем на совпадение. Если не совпало - в сад.
Таким образом, имеем сложность O(n).
1
-=ЮрА=-
Заблокирован
Автор FAQ
25.08.2011, 21:36 #26
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Воодится число тестов. Далее каждый тест содержит 2 строки. Подстроку и текст. Надо найти количество подстрок в тексте.
количество подстрок в тексте = число тестов; изначально мозг сломал пока понял как это просто
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:44  [ТС] #27
ValeryLaptev, спасибо, попробую

Добавлено через 3 минуты
Цитата Сообщение от Сыроежка Посмотреть сообщение
И я не вижу никакой "префикс-функции". Я вижу цикл while, который ни разу не исполн
Вот этот код откомпиллируй и посмотри что не выполняется ни разу
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
 string str1;
 string str2;
 string str;
 int i,n,m,q=0,t,k,a;
 int *mas;
 cin >> t;
 mas=(int*)malloc(1010002*sizeof(int));
 while (t--)
  {
   cin >> str2;
   cin >> str1;  
   n=str1.length();
   m=str2.length();
   
   str=str2+'#'+str1; mas[0]=0;
   a=0; k=0; q=0;
   for(i=1; i<n+m+1; i++)
    {         
     while((k>0) && (str[k]!=str[i])) { k=mas[k-1]; cout << "shit" << endl; }
     if (str[k]==str[i]) k++;
     if (k==m) q++;
     mas[i]=k;
    }
   cout << q << endl;
  }
 return 0;
}
Все знают что такое префикс, КМП, а ты какие-то выкрутасы открываешь, которые между прочем из стандартных библиотек, а они все используют примитивные алгоритмы.
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
25.08.2011, 21:53 #28
Цитата Сообщение от AvengerAlive Посмотреть сообщение
xAtom, откомпиллируй, проверь... Он на тест
ababa
aba
Выдаёт ответ 1
На тест
azabbazazabbaza
aza
выдаёт 3
а на azabbazazabbazazabbazazazabb
ответ вообще 5. Не работает...
Программа у xAtom абсолютно рабочая. Надо же анализировать уметь. Просто есть варианты когда подстроки могут или не могут пересекаться. У xAtom предусмотрено, что не могут, а если могут, то поменяйте строчку
C++
1
str += size;
на
C++
1
str++;
Другое дело в скорости.
0
easybudda
Модератор
Эксперт CЭксперт С++
9698 / 5648 / 964
Регистрация: 25.07.2009
Сообщений: 10,866
25.08.2011, 21:57 #29
без понятия, что там со скоростью...
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define SUB_LEN 10000
#define STR_LEN 1000000
 
int main(void){
    char * sub, * str, * ptr;
    int cnt, len;
    
    if ( ! ( sub = malloc(SUB_LEN) ) ){
        perror("malloc for sub");
        exit(1);
    }
    if ( ! ( str = malloc(STR_LEN) ) ){
        perror("malloc for str");
        exit(1);
    }
    
    while ( fgets(str, STR_LEN, stdin) && *str != '\n' && fgets(sub, SUB_LEN, stdin) && *sub != '\n' ){
        if ( ptr = strrchr(sub, '\n') )
            *ptr = 0;
        len = strlen(sub);
        for ( ptr = strstr(str, sub), cnt = 0; ptr && ++cnt; ptr = strstr(ptr + len, sub) )
            ;
        printf("%d meetings.\n", cnt);
    }
    
    free(sub);
    free(str);
    exit(0);
}
да, и подстроки не должны накладываться...
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:57  [ТС] #30
Olga_, ок спс
0
25.08.2011, 21:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.08.2011, 21:57
Привет! Вот еще темы с ответами:

Поиск подстрок в строках и вывод в файл - C++
Дан файл, html код страницы, в котором есть повторения типа &quot;email: password&quot;, например: lal@mail.ru: TXGgQ32Bh8J7PQn6J ...

Свертка повторяющихся подстрок по следующим правилам - C++
Помогите, не могу понять задание. В заданной строке символов выполнить свертку повторяющихся подстрок по следующим правилам: а)...

Найти количество вхождений подстрок в строку - C++
Собственно, в input.txt лежит строка размером до 250 символов, в output.txt нужно найти количество вхождений в нее подстрок, а именно...

Выделить все вхождения подстрок, заключенных в скобки - C++
Выдали задание по учебной практике, 1-ый курс учусь,пока с программированием туго. Помогите описать функцию работы со строкой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.