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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
#1

Нужно оптимизировать - C++

11.11.2012, 13:24. Просмотров 2304. Ответов 16
Метки нет (Все метки)

Есть задание, есть готовый код. Но он не проходит скоростной режим, нужно оптимизировать, помогите плз)

Требуется найти количество строк заданной длины n, состоящих из латинских строчных букв, не содержащих s в качестве подстроки. Поскольку количество подстрок может быть велико, выведите ответ по модулю 1000000007.

Входные данные:

Первая строка содержит число n(1 ≤ n ≤ 1000) - длину требуемых строк. Следующая строка содержит s которая также состоит только из строчных латинских букв, длина этой запрещенной строки m(1 ≤ m ≤ n).

Выходные данные:

Единственное число - количество возможных строк по модулю 1000000007.

Входные данные
1
a
Выходные данные
25
Входные данные
3
aa
Выходные данные
17525
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
#include <iostream>
#include <string.h>
using namespace std;
unsigned long int kol=0;;
int n,m;
char *a,*s;
int Perebor(int k)
{
char c;
if(k==n)
{  if (!strstr(a,s)) kol++;
  return 0;
}
 
for(c='a';c<='z';c++)
{
  a[k]=c;
  a[k+1]='\0';
  if(!strstr(a,s)) Perebor(k+1);
}
return 1;
}
int main()
{
  cin>>n;
  a=new char[n+1];
  s=new char[n+1];
  cin>>s;
  m=strlen(s);
  a[n]='\0';
  Perebor(0);
  kol=kol%1000000007;
  cout<<kol<<endl;
  return 0;
}
При последнем тесте время выходит за границу 2-х секунд.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
damnik
0 / 0 / 0
Регистрация: 11.11.2012
Сообщений: 5
11.11.2012, 19:56     Нужно оптимизировать #2
Перебрать в этой задаче не получится, это слишком долго. Эта задача достаточно известна и решается при помощи суффиксного автомата (подробнее http://e-maxx.ru)

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;
 
#pragma comment(linker, "/stack:64000000")
 
 
struct state 
{
    int len, link;
    map<char,int> next;
    bool stop;
    vector<int> dp;
    state():stop(false){}
};
const int MAXLEN = 100000;
state st[MAXLEN*2];
int sz, last;
long long rel = 9400193601397090LL;
void sa_init() 
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
}
void sa_extend (char c) 
{
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
        st[p].next[c] = cur;
    if (p == -1)
        st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len)
            st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                st[p].next[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
char buf[20];
char *tos(void*p)
{
    return (char*)p;
}
char *tos(int x)
{
    sprintf(buf,"%d",x);
    return buf;
}
 
int solve (string s, int k) {
    sa_init();
    for (int i=0; i<(int)s.length(); ++i)
        sa_extend (s[i]);
 
    for (int i = 0; i < sz; i++)
        st[i].dp.assign(k+1, 0);
    st[last].dp[0] = 1;
 
    for (int i = 0; i < k; i++)
        for (int j = 0; j < sz; j++){
            if (j != last){
                for (std::map<char, int>::iterator it = st[j].next.begin(); it != st[j].next.end(); ++it){
                    st[j].dp[i+1] += st[it->second].dp[i];
                    st[j].dp[i+1] %= 1000000007;
                }
                st[j].dp[i+1] += (st[0].dp[i] * (26LL - st[j].next.size())) % 1000000007;
            }
            else {
                st[j].dp[i+1] = (26LL * st[j].dp[i]) % 1000000007;
            }
        }
    return st[0].dp[k];
}
 
 
 
int qpow(int k, int p)
{
    long long cur = k;
    long long res = 1;
    while (p){
        if (p & 1){
            res *= cur;
            res %= 1000000007;
        }
        cur *= cur;
        cur %= 1000000007;
        p /= 2;
    }
    return (int)res;
}
 
 
int main()
{
    int k;
    cin >> k;
    string s;
    cin >> s;
    int re1 = qpow(26, k) - solve(s, k);
    printf("%s", re1 > 0 ? tos(abs(re1)) : tos(&rel));
#ifdef _DEBUG
    cout.flush();
    fflush(stdout);
    _exit(0);
#endif
    return 0;
}
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 20:20  [ТС]     Нужно оптимизировать #3
Самому скомпилировав этот код - всё работало правильно. Отослав его на сервер, мне пришло сообщение, что ответ неверен.

P.S. Олимпиада сейчас идет. Я думаю, что вы в курсе, но всё равно спасибо)
damnik
0 / 0 / 0
Регистрация: 11.11.2012
Сообщений: 5
11.11.2012, 20:27     Нужно оптимизировать #4
Цитата Сообщение от Basisd Посмотреть сообщение
Самому скомпилировав этот код - всё работало правильно. Отослав его на сервер, мне пришло сообщение, что ответ неверен.
А какой номер теста?
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 20:30  [ТС]     Нужно оптимизировать #5
Цитата Сообщение от damnik Посмотреть сообщение
А какой номер теста?
тест 3. со старым кодом был тест 5

Не по теме:

строки только один человек сделал, не вы ли это?)

Bringoff
СуперМодулятор
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
11.11.2012, 20:45     Нужно оптимизировать #6
А что за олимпиада?
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 20:47  [ТС]     Нужно оптимизировать #7
Цитата Сообщение от Izobara Посмотреть сообщение
А что за олимпиада?
http://volga-it.org/
V Поволжская олимпиада по информационным технологиям среди студентов и аспирантов "Волга ИТ - 2012"
damnik
0 / 0 / 0
Регистрация: 11.11.2012
Сообщений: 5
11.11.2012, 21:33     Нужно оптимизировать #8
Поправил. Там были проблемы с неудачно направленными ребрами.

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;
 
#pragma comment(linker, "/stack:64000000")
 
 
struct state 
{
    int len, link;
    map<char,int> next;
    bool stop;
    vector<int> dp;
    state():stop(false){}
};
const int MAXLEN = 100000;
state st[MAXLEN*2];
int sz, last;
long long rel = 9400193601397090LL;
void sa_init() 
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
}
void sa_extend (char c) 
{
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
        st[p].next[c] = cur;
    if (p == -1)
        st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len)
            st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                st[p].next[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
 
char buf[20];
char *tos(void*p)
{
    return (char*)p;
}
char *tos(int x)
{
    sprintf(buf,"%d",x);
    return buf;
}
 
int solve (string s, int k) {
    sa_init();
    for (int i=0; i<(int)s.length(); ++i)
        sa_extend (s[i]);
 
    for (char c = 'a'; c <= 'z'; c++)
        if (c != s[0])
            st[0].next[c] = 0;
    int cur = 0;
    for (int i=0; i<(int)s.length(); ++i)
    {
        char c = s[i];
        int p = cur;
        int q = st[p].next[c];
        st[q].link = (st[p].link == -1 ? 0 : st[st[p].link].next[s[i]]);
        if (i != s.length() - 1)
        {
            for (char c = 'a'; c <= 'z'; c++)
                if (c != s[i+1])
                    st[q].next[c] = (st[st[q].link].next[c]);
        }
        cur = q;
    }
 
    for (int i = 0; i < sz; i++)
        st[i].dp.assign(k+1, 0);
    st[0].dp[0] = 1;
 
    for (int i = 0; i < k; i++)
        for (int j = 0; j < sz; j++){
            if (j != cur){
                for (std::map<char, int>::iterator it = st[j].next.begin(); it != st[j].next.end(); ++it){
                    st[it->second].dp[i+1] += st[j].dp[i];
                    st[it->second].dp[i+1] %= 1000000007;
                }
            }
            else {
                st[j].dp[i+1] += (26LL * st[j].dp[i]) % 1000000007;
            }
        }
    return st[cur].dp[k];
}
 
 
 
int qpow(int k, int p)
{
    long long cur = k;
    long long res = 1;
    while (p){
        if (p & 1){
            res *= cur;
            res %= 1000000007;
        }
        cur *= cur;
        cur %= 1000000007;
        p /= 2;
    }
    return (int)res;
}
 
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int k;
    cin >> k;
    string s;
    cin >> s;
    int re1 = qpow(26, k) - solve(s, k);
    printf("%s", re1 > 0 ? tos(abs(re1)) : tos(&rel));
#ifdef _DEBUG
    cout.flush();
    fflush(stdout);
    _exit(0);
#endif
    return 0;
}
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 21:56  [ТС]     Нужно оптимизировать #9
Не люблю в чужом коде копаться до жути)

Пробежался я, удалил две строчки:
C++
1
2
freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
ибо они там критично не нужны. но ни так ни сяк не компилировалось, выдало несколько вариантов ошибок, изза чего может быть:

• Решение вывело данные не в требуемом формате, не вывело данные целиком или вывело лишние данные.
• Файл не сохранён в среде разработки или на проверку отправлен ошибочный файл.
• Решение содержит неинициализированные переменные.
• Используется значение итерационной переменной после цикла for.
• Решение выводит данные в файл output.txt (должно в консоль).
• Если решение на Delphi, возможно отсутствует строка uses SysUtils;.
на компиляторе выводило всё нормльно, вывод в output.txt я выключил... Тест 12. Сможете помочь или на этом всё?)
damnik
0 / 0 / 0
Регистрация: 11.11.2012
Сообщений: 5
11.11.2012, 21:59     Нужно оптимизировать #10
Про файлы извиняюсь жутко, забыл убрать. Так проверять удобнее.

А 12 тест какой вердикт?
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 22:04  [ТС]     Нужно оптимизировать #11
Цитата Сообщение от damnik Посмотреть сообщение
А 12 тест какой вердикт?
Если честно, я и сам не знаю, что это означает. Я написал лишь возможные причины, почему может не работать) Просто выдало: "Presentation Error" и всё тут...
banme!
Сообщений: n/a
11.11.2012, 22:17     Нужно оптимизировать #12
Цитата Сообщение от Basisd Посмотреть сообщение
Просто выдало: "Presentation Error" и всё тут...
Да, действительно PE. Ведь ban is not longint!
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 22:26  [ТС]     Нужно оптимизировать #13
Цитата Сообщение от banme! Посмотреть сообщение
Да, действительно PE. Ведь ban is not longint!

Не по теме:

меня терзают смутные сомненья, но всё же...



Как понять ваше сообщение?)
heapsort
Сообщений: n/a
11.11.2012, 22:51     Нужно оптимизировать #14
Цитата Сообщение от Basisd Посмотреть сообщение
Если честно, я и сам не знаю, что это означает. Я написал лишь возможные причины, почему может не работать) Просто выдало: "Presentation Error" и всё тут...
Попробуйте следующий тест:

999
abaca
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 22:58  [ТС]     Нужно оптимизировать #15
Цитата Сообщение от heapsort Посмотреть сообщение
Попробуйте следующий тест:

999
abaca
А вы веселые ребята, мне понравилось с вами общаться) На этом действия свои сворачиваю, жду окончания олимпиады и архива с решениями задач (надо же научиться делать эту задачу). Ведь программист учится только на поставленных задачах, на практике и никак иначе.

Не по теме:

и кстати, с первого сообщения в этой теме я заподозрил неладное. спасибо вам за хороший вечер, милые анонимусы



Все, вопрос решен, тему можно закрывать.
damnik
0 / 0 / 0
Регистрация: 11.11.2012
Сообщений: 5
12.11.2012, 15:33     Нужно оптимизировать #16
Олег, чтобы научиться решать задачи, нужно решать их самому. Других вариантов нет. Разбор - это круто, например, в этой задаче есть решение строк на 70. Но разбор, который, к тому же, формально будет прочитан, никогда не расскажет вам "следы" подобных конструкций. Т.е. не научит решать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2012, 15:32     Нужно оптимизировать
Еще ссылки по теме:

C++ Оптимизировать код
C++ Нужно оптимизировать функцию
C++ Нужно оптимизировать программу сложность с циклами и условными операторами
Исправить и оптимизировать код C++
Оптимизировать код C++

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

Или воспользуйтесь поиском по форуму:
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
13.11.2012, 15:32  [ТС]     Нужно оптимизировать #17
Цитата Сообщение от damnik Посмотреть сообщение
Олег, чтобы научиться решать задачи, нужно решать их самому. Других вариантов нет. Разбор - это круто, например, в этой задаче есть решение строк на 70. Но разбор, который, к тому же, формально будет прочитан, никогда не расскажет вам "следы" подобных конструкций. Т.е. не научит решать.
Я частично с Вами не согласен.

Когда я только начал учить С++, я столкнулся с самой огромной для меня проблемой - я не понимал как работает цикл. Пока я не пересмотрел десяток простых программ, сам я так и не смог вникнуть в сей цикл. Мне никто не помогал, но я с помощью ЧУЖОГО тогда разобрался в этом САМ.

И разбор решений в моем понимании является не "перечитка" чужого кода, а главное понимание этого кода. Нужно постараться уловить мысль другого автора, научиться новой изюминке.
Yandex
Объявления
13.11.2012, 15:32     Нужно оптимизировать
Ответ Создать тему
Опции темы

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