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

@Basisd · Регистрация: 09.12.2010

Студворк — интернет-сервис помощи студентам

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

Требуется найти количество строк заданной длины 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 · 11.11.2012, 19:56

Перебрать в этой задаче не получится, это слишком долго. Эта задача достаточно известна и решается при помощи суффиксного автомата (подробнее 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 · 11.11.2012, 20:20 **[ТС]**

Самому скомпилировав этот код - всё работало правильно. Отослав его на сервер, мне пришло сообщение, что ответ неверен.

P.S. Олимпиада сейчас идет. Я думаю, что вы в курсе, но всё равно спасибо)

@damnik · 11.11.2012, 20:27

Сообщение от Basisd

Самому скомпилировав этот код - всё работало правильно. Отослав его на сервер, мне пришло сообщение, что ответ неверен.

А какой номер теста?

@Basisd · 11.11.2012, 20:30 **[ТС]**

Сообщение от damnik

А какой номер теста?

тест 3. со старым кодом был тест 5

Не по теме:

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

Bringoff · 11.11.2012, 20:45

А что за олимпиада?

@Basisd · 11.11.2012, 20:47 **[ТС]**

Сообщение от Izobara

А что за олимпиада?

http://volga-it.org/
V Поволжская олимпиада по информационным технологиям среди студентов и аспирантов "Волга ИТ - 2012"

@damnik · 11.11.2012, 21:33

Поправил. Там были проблемы с неудачно направленными ребрами.

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 · 11.11.2012, 21:56 **[ТС]**

Не люблю в чужом коде копаться до жути)

Пробежался я, удалил две строчки:

C++
1
2
freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);

ибо они там критично не нужны. но ни так ни сяк не компилировалось, выдало несколько вариантов ошибок, изза чего может быть:

• Решение вывело данные не в требуемом формате, не вывело данные целиком или вывело лишние данные.
• Файл не сохранён в среде разработки или на проверку отправлен ошибочный файл.
• Решение содержит неинициализированные переменные.
• Используется значение итерационной переменной после цикла for.
• Решение выводит данные в файл output.txt (должно в консоль).
• Если решение на Delphi, возможно отсутствует строка uses SysUtils;.

на компиляторе выводило всё нормльно, вывод в output.txt я выключил... Тест 12. Сможете помочь или на этом всё?)

@damnik · 11.11.2012, 21:59

Про файлы извиняюсь жутко, забыл убрать. Так проверять удобнее.

А 12 тест какой вердикт?

@Basisd · 11.11.2012, 22:04 **[ТС]**

Сообщение от damnik

А 12 тест какой вердикт?

Если честно, я и сам не знаю, что это означает. Я написал лишь возможные причины, почему может не работать) Просто выдало: "Presentation Error" и всё тут...

11.11.2012, 22:17

Сообщение от Basisd

Просто выдало: "Presentation Error" и всё тут...

Да, действительно PE. Ведь ban is not longint!

@Basisd · 11.11.2012, 22:26 **[ТС]**

Сообщение от banme!

Да, действительно PE. Ведь ban is not longint!

Не по теме:

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

Как понять ваше сообщение?)

11.11.2012, 22:51

Сообщение от Basisd

Если честно, я и сам не знаю, что это означает. Я написал лишь возможные причины, почему может не работать) Просто выдало: "Presentation Error" и всё тут...

Попробуйте следующий тест:

999
abaca

@Basisd · 11.11.2012, 22:58 **[ТС]**

Сообщение от heapsort

Попробуйте следующий тест:

999
abaca

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

Не по теме:

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

Все, вопрос решен, тему можно закрывать.

@damnik · 12.11.2012, 15:33

Олег, чтобы научиться решать задачи, нужно решать их самому. Других вариантов нет. Разбор - это круто, например, в этой задаче есть решение строк на 70. Но разбор, который, к тому же, формально будет прочитан, никогда не расскажет вам "следы" подобных конструкций. Т.е. не научит решать.

@Basisd · 13.11.2012, 15:32 **[ТС]**

Сообщение от damnik

Олег, чтобы научиться решать задачи, нужно решать их самому. Других вариантов нет. Разбор - это круто, например, в этой задаче есть решение строк на 70. Но разбор, который, к тому же, формально будет прочитан, никогда не расскажет вам "следы" подобных конструкций. Т.е. не научит решать.

Я частично с Вами не согласен.

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

И разбор решений в моем понимании является не "перечитка" чужого кода, а главное понимание этого кода. Нужно постараться уловить мысль другого автора, научиться новой изюминке.

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

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

Bringoff СуперМодулятор 134 / 134 / 48 Регистрация: 03.11.2012 Сообщений: 974
	11.11.2012, 20:45
	А что за олимпиада? 0

@damnik 0 / 0 / 0 Регистрация: 11.11.2012 Сообщений: 5
	11.11.2012, 21:59
	Про файлы извиняюсь жутко, забыл убрать. Так проверять удобнее. А 12 тест какой вердикт? 0

@damnik 0 / 0 / 0 Регистрация: 11.11.2012 Сообщений: 5
	12.11.2012, 15:33
	Олег, чтобы научиться решать задачи, нужно решать их самому. Других вариантов нет. Разбор - это круто, например, в этой задаче есть решение строк на 70. Но разбор, который, к тому же, формально будет прочитан, никогда не расскажет вам "следы" подобных конструкций. Т.е. не научит решать. 0