06_Rup3. Различные словаДана строка S состоящая из N символов. Назовем ее подстрокой Sij строку с i-го по j-й символ (i <= j). Ваша задача — посчитать количество различных подстрок заданной строки.
Формат ввода:
Во входном файле находится одна непустая строка, состоящая из маленьких латинских букв, длиной не более чем 1024 символа.
Формат вывода:
Выходной файл должен содержать одно число — количество различных подстрок строки S.
Пример ввода: Пример вывода:
Abc 6
Пример ввода: Пример вывода:
Aaa 3
Такую работу по определению делает set
{code:title=setwork.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream cin("words.in");
ofstream cout("words.out");
set <string> SS;
string s;
int i,j,d;
cin >> s;
d=s.length();
for (i=0; i<d; i++)
for (j=i; j<d; j++)
SS.insert(s.substr(i,j-i+1));
cout << SS.size();
}{code}
К сожалению, при данных ограничениях приведенное решение не проходит по времени.
Используем unordered set (оно использует хеш-таблицу)
{code:title=time.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream cin("words.in");
ofstream cout("words.out");
unordered_set<string> SS;
string s;
int i,j,d;
cin >> s;
d=s.length();
for (i=0; i<d; i++)
for (j=i; j<d; j++)
SS.insert(s.substr(i,j-i+1));
cout << SS.size();
}{code}
Такое решение не проходит по памяти
Используем hash от строки, чтобы хранить и сравнивать не сами строки, а только их хеши
{code:title=bigall.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

#define HM 100000000000000007
#define HA 100000000007
#define HB 101

long long hash_f(string s)
{
unsigned int i;
long long res=1;
for (i=0; i<s.length(); i++)
res+=(1LL*res*HA + (s[i]-'a') + HB)%HM;
return res%HM;
}

int main()
{
ifstream cin("words.in");
ofstream cout("words.out");
unordered_set<long long> SS;
string s;
int i,j,d;

cin >> s;
d=s.length();
for (i=0; i<d; i++)
for (j=i; j<d; j++)
SS.insert(hash_f(s.substr(i,j-i+1)));
cout << SS.size();
}
{code}
Такое решение не проходит по времени начиная с 15-го теста

Используем rolling_hash - модифицируя хеш, при добавлении нового символа
И это уже полное решение, которое проходит все тесты.
{code:title=all.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

#define HA 1000000007
#define HB 101
/* Given the hash 'h' of string S, computes the hash of S + 'ch'. */
long long rolling_hash(long long h, int ch)
{
return (1ll * h * HA + ch + HB);
}

int main()
{
ifstream cin("words.in");
ofstream cout("words.out");
unordered_set<long long> SS;
string s;
int i,j,d;
long long h;

cin >> s;
d=s.length();
for (i=0; i<d; i++)
for (j=i, h=1; j<d; j++)
{
h=rolling_hash(h,s[j]);
SS.insert(h);
}
cout << SS.size();
}
{code}
Заметим что С++ позволяет писать и так (сокращая решение на 3 строки ):
{noformat}
for (i=0; i<d; i++)
for (j=i, h=1; j<d; j++)
SS.insert(h=rolling_hash(h,s[j]));{noformat}