九度 oj 题目1555：重复子串

http://ac.jobdu.com/problem.php?pid=1555

这道题觉得还可以再优化，暂时先水过了。

#include <iostream> #include <string> #include <set> using namespace std; #define rep(i,j,k) for(int i=j;i<=k;i++) string s; int cal(string s) { set<string> uniq; int len = s.size(); rep(i, 0, len - 1) rep(j, i + 1, len) { string sub = s.substr(i, j - i); //string suffix = s.substr(j); string::size_type idx = s.find(sub,j); if (idx != string::npos) { uniq.insert(sub); // cout << sub << endl; } else break; //第一次没过，差了一个剪枝 } return uniq.size(); } int main() { while (cin >> s) { cout << cal(s) << endl; } return 0; }