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

Найти все вхождения строки s в t - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Сформировать файл целых чисел http://www.cyberforum.ru/cpp-beginners/thread31171.html
составить програму,которая формирует файлцелых чисел,получаемых с помощу датчика случайных чисел
C++ Структура сведения о каждом химическом елементе таблицы Менделеева представить виде структуры.написать прорму ввода таблицы в память компютера. http://www.cyberforum.ru/cpp-beginners/thread31170.html
Program received signal SIGSEGV, Segmentation fault C++
Когда запускаю дебагер: gdb ./preci Вюдает следуще. Я не могу понять с чем это могет быть связано. Код: GNU gdb 6.4.90-debian Copyright (C) 2006 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions.
C++ Тестирующие сайты..
Кто решает задачи на этих тестирующих сайтах, отзовитесь и помогите решить некоторые задачи:, www.********, www.acmu.ru
C++ Комбинаторика... http://www.cyberforum.ru/cpp-beginners/thread31033.html
Обмен валюты (Время: 1 сек. Память: 16 Мб Сложность: 70%) Петя работает в обменном пункте во Флатландии. Недавно Петя получил от начальства набор цифр для отображения обменного курса. К сожалению, набор содержит всего по две копии каждой цифры. Теперь Петя хочет узнать, сколько различных обменных курсов он сможет отобразить. Петя обменивает флатландские доллары на крайландские тугрики. Петя...
C++ Использование файлов и строк Уважаемые программисты! Нужна ваша помощь, заканчиваю написание диплома и возникла следующая проблемка: Есть программа, которая все результаты записывает в файл txt. Этот файл имеет следующий вид: time 0.000 0.000 0.250 0.000 0.000 0.000 0.000 ... time 0.050 0.000 0.250 0.000 0.000 0.000 0.000 ... time 0.100 0.000 0.250 0.000 0.000 0.000 0.000 ... ... подробнее

Показать сообщение отдельно
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
23.04.2009, 21:40  [ТС]     Найти все вхождения строки s в t
Gravity, я так сделал но TLE мне нужно какимто алгоритмом кнута сделать...

Добавлено через 2 часа 28 минут 18 секунд
Нууу... никто не может сделать.... Вот функция никак в прогу запихнуть не могу...
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
int  seek_substring_KMP  (char s[],   char q[])
    { 
    int  i, j, N, M; 
    N = strlen(s); 
    M = strlen(q); 
    int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/ 
    i=0; 
    j=-1;
    d[0]=-1;
    while(i<M-1)
        {
        while((j>=0) && (q[j]!=q[i]))
            j = d[j];
        i++;
        j++;
        if(q[i]==q[j])
            d[i]=d[j];
        else
            d[i]= j;
        }
    /* поиск */
    for(i=0,j=0;(i<=N-1)&&(j<=M-1); i++,j++)
        while((j>=0)&&(q[j]!=s[i]))
            j=d[j];
    free (d);  /* освобождение памяти массива d */ 
    if (j==M)
        return i-j;
    else /* i==N */ 
        return -1;
    }
Добавлено через 1 час 52 минуты 16 секунд
Ну кто нибудь попытайтесь...

Добавлено через 1 час 36 минут 54 секунды
Никто в реале не может написать прогу????

Добавлено через 22 минуты 26 секунд
может исправите....
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include<string.h>
int search(char s[200000],   char q[200000])
        { 
        int  i, j, N, M; 
        N = strlen(s); 
        M = strlen(q); 
        int *d = new int [M];
        i=0; 
        j=-1;
        d[0]=-1;
        while(i<M-1)
                {
                while((j>=0) && (q[j]!=q[i]))
                        j = d[j];
                i++;
                j++;
                if(q[i]==q[j])
                        d[i]=d[j];
                else
                        d[i]= j;
                }
        for(i=0,j=0;(i<=N-1)&&(j<=M-1); i++,j++)
                while((j>=0)&&(q[j]!=s[i]))
                        j=d[j];
        if (j==M)
                return i-j;
        else 
                return -1;
        }
int main()
{
    char sen[200000],sen1[200000],sen2[200000];
    int x,i,l1,l2,j=0,k=0;
    gets (sen);l2=strlen(sen);
    gets (sen1);l1=strlen(sen1);
    x=search(sen,sen1);
    //printf ("%d ",x);
    while (j!=l2-l1){
          for (i=(x+l1); i<l2; i++){
              sen2[k]=sen[i];
              printf ("%c",sen2[k]);
              k++;
              }
          x=search(sen2,sen1);
          printf ("\n");
          j+=l1-1;
          }
    getchar();
    return 0;
}
 
Текущее время: 21:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru