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

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

Восстановить пароль Регистрация
 
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155
26.02.2014, 04:15     Какая разница между двумя алгоритмами? #1
Вообщем, как только я свою задачу не упрощал, но в указанные ограничения она так и не входит. Сначала был лимит памяти, теперь лимит времени и это наверно уже 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 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2014, 04:15     Какая разница между двумя алгоритмами?
Посмотрите здесь:

C++ Какая разница между cin и getline?
C++ Какая разница между cin и scanf?
C++ Разница между двумя идентичными программами
C++ Какая разница между eof и просто объектом?
C++ Разница между двумя библиотеками потоков
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155
26.02.2014, 04:45  [ТС]     Какая разница между двумя алгоритмами? #2
Почитать про поиск наибольшей общей подстроки можно http://ru.wikipedia.org/wiki/%D0%9D%...BE%D0%BA%D0%B0
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,154
Завершенные тесты: 1
26.02.2014, 07:51     Какая разница между двумя алгоритмами? #3
1. Использование контейнерных строк STL существенно увеличивает время вычислений.
2. У Вас в алгоритме 3 вложенных цикла for, а в найденном только два.
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155
26.02.2014, 13:38  [ТС]     Какая разница между двумя алгоритмами? #4
Цитата Сообщение от zss Посмотреть сообщение
1. Использование контейнерных строк STL существенно увеличивает время вычислений.
Ну ведь не настолько, чтобы при одинаковых входных данных моя программа обрабатывала бы 30 секунд, а найденная - 6 сек. Да я даже заменял контейнер на указатель строк и всё также...

Цитата Сообщение от zss Посмотреть сообщение
2. У Вас в алгоритме 3 вложенных цикла for, а в найденном только два.
Да нет, если Вы внимательно посмотрите, то увидите в строке 38 (найденного когда) первый цикл for. В строке 39 вызывается функция, в которой - 2 цикла for.
Yandex
Объявления
26.02.2014, 13:38     Какая разница между двумя алгоритмами?
Ответ Создать тему
Опции темы

Текущее время: 08:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru