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

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

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

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

11.11.2012, 13:24. Просмотров 2338. Ответов 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-х секунд.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2012, 13:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нужно оптимизировать (C++):

Нужно оптимизировать функцию - C++
Немножко не шарю но она должна сортировать пузырьком: #include &lt;iostream&gt; #include &lt;time.h&gt; using namespace std; int pokerface...

Нужно оптимизировать код - C++
Вобщем код не принемает сайт, немного нагружает и по времени не проходит задание Август и Беатриса играют в игру. Август загадал...

Слишком долгий перебор - нужно оптимизировать - C++
Задача с ацмп.ру: Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок. Задача легкая, но в...

Нужно оптимизировать программу сложность с циклами и условными операторами - C++
Здравствуйте. Недели 2 пытаюсь кодить на с++, что-то получается, что-то не очень. Прошу отвечать только по существу. За указания на...

Нужно оптимизировать готовый код, чтобы не было стыдно показать - C++
Мне дали сделать задачку, чтобы проверить мои знания в ООП (я только 2 месяца назад начал изучать С++). И так, задача: Я написал...

Оптимизировать перебор - C++
Неделю учу С++, так что прошу не гадить. Надо уменьшить время работы. Задача: Вступление — Брат мой, Магистр Ордена хочет узнать...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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;
}
0
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 20:20  [ТС] #3
Самому скомпилировав этот код - всё работало правильно. Отослав его на сервер, мне пришло сообщение, что ответ неверен.

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

Не по теме:

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

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

А 12 тест какой вердикт?
0
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.11.2012, 22:04  [ТС] #11
Цитата Сообщение от damnik Посмотреть сообщение
А 12 тест какой вердикт?
Если честно, я и сам не знаю, что это означает. Я написал лишь возможные причины, почему может не работать) Просто выдало: "Presentation Error" и всё тут...
0
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!

Не по теме:

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



Как понять ваше сообщение?)
0
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
А вы веселые ребята, мне понравилось с вами общаться) На этом действия свои сворачиваю, жду окончания олимпиады и архива с решениями задач (надо же научиться делать эту задачу). Ведь программист учится только на поставленных задачах, на практике и никак иначе.

Не по теме:

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



Все, вопрос решен, тему можно закрывать.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2012, 22:58
Привет! Вот еще темы с ответами:

Оптимизировать код - C++
Доброго времени суток, как можно оптимизировать код что бы он быстрее работал ? Дана последовательность из n чисел a1, a2,..., an. C...

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

Оптимизировать код - C++
Первое число входного потока - количество чисел Дальше идут те самые числа Надо найти кол-во пар чисел, для которых выполняется nums &lt;=...

Оптимизировать алгоритм - C++
Приятель подкинул задачку: Получить новую матрицу В, элемент b которой равен наименьшему из элементов a исходной матрицы, где k меняется...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.11.2012, 22:58
Ответ Создать тему
Опции темы

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