Просмотр источника
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} |