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

Какая разница между двумя алгоритмами? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Функция перевода из 16-ричной системы счисления в десятичную http://www.cyberforum.ru/cpp-beginners/thread1105670.html
Есть ли в си++ такая фун-я?
C++ Определить размер текста, вводимого пользователем и записывается в файлы Определить размер текста, вводимого пользователем и записывается в файлы.Результаты вывести на экран. Помогите пожалуйста,срочно надо очень !!! http://www.cyberforum.ru/cpp-beginners/thread1105668.html
Напишите программу на языке программирования С#, в которой создан класс Massive, включающий метод для ввода значений элементов массива C++
Напишите программу на языке программирования С#, в которой создан класс Massive, включающий метод для ввода значений элементов массива, метод для сортировки массива и метод для вывода отсортированного массива на экран. Пользователь задает значения элементов массива
CharToInt C++
нужно перевести 16ричную строку в тип int идея - с тем чтоб часть перевести в atoi'ем а при встрече букв case'ом выполнить переход к соответствущими числу, а потом сделать конкатенацию двух переводов - адекватная?
C++ В чем ошибка? http://www.cyberforum.ru/cpp-beginners/thread1105653.html
В текстовом док файле куча символов а оно стрянет на первых 7-ми только( #include <iostream> #include <fstream> #include <conio.h> #include <locale> #include <string> #include <cstdlib> #include <iomanip> using namespace std;
C++ Заполнение матрицы Есть программа, которая запрашивает у пользователя размер матрицы, а потом заполняет ее случайными числами. Так вот, моя программы при вводе числа B меньшего A ломается. Не могу понять, где моя ошибка. Подскажите пожалуйста. #include<iostream> #include <ctime> #include <iomanip> #include <stdlib.h> using namespace std; int A,B; подробнее

Показать сообщение отдельно
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155

Какая разница между двумя алгоритмами? - C++

26.02.2014, 04:15. Просмотров 298. Ответов 3
Метки (Все метки)

Вообщем, как только я свою задачу не упрощал, но в указанные ограничения она так и не входит. Сначала был лимит памяти, теперь лимит времени и это наверно уже 10 версия программы. В итоге я задолбался и решил загуглить подобные решения задачи: "Поиск наибольшей общей подстроки". И нашел вариант кода, который к удивлению в разы быстрей работает, хотя на глаз и не увидишь различия (алгоритм, кстати, одинаковый). Я не знаю, магия ли это какая-та или я просто устал уже и не замечаю, вообщем жду ваших ответов.

Мой код:
Кликните здесь для просмотра всего текста
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
//#include <conio.h>
 
using namespace std;
 
//функтор сортировки строк по размеру.
struct SortBySize 
{
    bool operator()(string first, string second)
        {
            //сортировка по алфавиту, при одинаковых размерах.
            if (first.size()==second.size())
                return (first<second); 
 
            //сортировка по размеру.
            return (first.size()<second.size());
        }
} SortBySize;
 
 
int main()
{
 
    int k=0; //число строк.
    cin>>k;
    int i, j, t;
 
    vector<string> Str(k); //контрейнер строк.
    
    //считываем строки.
    for (i=0; i<k; i++)
    {
        cin>>Str[i];
        cin.ignore(1, '\n'); //пропускаем EOL.
    }
 
    //если дана одна строка.
    if (k==1) 
        cout<<Str[0]<<endl;
    else //строк больше одной.
    {
        //сортируем строки по размеру (возрастание).
        sort (Str.begin(), Str.end(), SortBySize); 
 
        string subs; //подстрока.
        subs=Str[0]; //используем 1-ю строку, как шаблон подстроки.
        int* entry;
        int* temp;
        int maxLength=0; //максимальная длина подстроки.
        int indTail=0; //индекс хвоста подстроки.
 
        //поиск подстроки.
        for (t=1; t<k; t++) //перебор строк.
        {
            entry=new int[Str[t].size()](); //цепочка вхождений.
            temp=new int[Str[t].size()](); //вспомогательная цеп. вхождений.
 
            for (i=0; i<subs.size(); i++) //перебор эл. подстроки.
            {
                for (j=0; j<Str[t].size(); j++) //перебор эл. строки.
                    if (subs[i]==Str[t][j])
                    {
                        //рзамер текущего будет = размер предыдущего - 
                        // каскадно расположенного позади сверху (или 0, если его нет) + 1.
                        temp[j]=(j==0?0:entry[j-1])+1; 
                        if (temp[j]>maxLength) //обновляем размерность и индекс подстроки.
                        {
                            maxLength=temp[j];
                            indTail=j;
                        }
 
                    }
                    else
                        temp[j]=0;
 
                //обмениваем цепочки вхождения.
                swap(entry, temp);
            }
 
            //тут уже полностью перебрали строку, получили данные о новой подстроке,
            // выделим подстроку (на основе данных).
            subs=Str[t].substr(indTail-maxLength+1, maxLength);
            maxLength=0;
            indTail=0;
        }
 
        cout<<subs<<endl;
            
    }
 
    //getch();
    return 0;
}


Найденный:
Кликните здесь для просмотра всего текста
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <string.h>
#include <time.h>
#include <conio.h>
 
using namespace std;
const int  MAX=10000;
char** _strings=new char*[10];
int len;
 
char* GetLargestCommonSubstring( char* str1, char* str2 );
inline void readNomberSubstrings();
inline const char* getMaxSubstring();
 
int main()
{
    readNomberSubstrings();
    cout<< getMaxSubstring();
    getch();
    return 0;
}
 
void readNomberSubstrings()
{
    cin>>len;
 
    for(int i=0; i<len;i++)
        _strings[i]=new char[MAX];
 
    for(int i=0; i<len; i++)
        cin>>_strings[i];
}
 
 const char* getMaxSubstring()
{
    char *maxSubstring=_strings[0];
    //long T=clock();
    for(int i=1; i < len; i++)
        maxSubstring=GetLargestCommonSubstring(maxSubstring, _strings[i]);
    //cout<<clock()-T<<endl;
    return maxSubstring;
}
 
char* GetLargestCommonSubstring( char* str1, char* str2 ) {
 
    int strLen2=strlen(str2);
    const int solution_size = strLen2+ 1;
 
    int *x=new int[solution_size]();
    int *y= new int[solution_size]();
 
    int **previous = &x;
    int **current = &y;
 
    int max_length = 0;
    int result_index = 0;
 
    int j;
    int length;
    int J=strLen2 - 1;
 
    for(int i = strlen(str1) - 1; i >= 0; i--)
    {
        for(j = J; j >= 0; j--) 
        {
            if(str1[i] != str2[j]) 
                (*current)[j] = 0;
            else 
            {
                length = 1 + (*previous)[j + 1];
                if (length > max_length)
                {
                    max_length = length;
                    result_index = i;
                }
 
                (*current)[j] = length;
            }
        }
 
        swap(previous, current);
    }
    str1[max_length+result_index]='\0';
    return &(str1[result_index]);
}


Входные данные прикреплены к теме.

P.S. Число в начале - количество строк.
Вложения
Тип файла: rar test.rar (7.2 Кб, 3 просмотров)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 10:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru