字符串的不同字串个数

给定长度为\(n\)的字符串\(s\),求该字符串的不同字串的个数

朴素暴力

时间复杂度\(O(n^3logn)\)

枚举子串的左右端点，取出后使用set去重

string s;
set<string> ans;
for (int l = 0; l < s.length();l++){
    for (int r = l; r < s.length();r++){
        string t;
        for (int i = l; i <= r;i++)
            t += s[i];
        ans.insert(t);
    }
}
cout << ans.size();

很显然，这样暴力的做法无法通过任何\(n \geq 1000\)的题目

hash

时间复杂度\(O(n^2logn)\)

同样使用暴力枚举字串的左右端点，但是使用字符串hash优化取出字串的步骤（优化了一个\(n\)的复杂度）。同样使用set去重

hashv gethash(int l, int r); /* ...hash函数 */

int main(){
    string s;
    set<hashv> ans;
    for (int l = 0; l < s.length();l++){
        for (int r = l; r < s.length();r++){
            hashv h = gethash(l, r);
            ans.insert(h);
        }
    }
    cout << ans.size();
}

对于较为简单的题目，字符串哈希的复杂度已经可以通过，但是很显然，这种算法对于\(n \geq 10^4\)的题目依然不够优秀，而且字符串哈希实现起来也较为麻烦，实现不够优秀的字符串哈希甚至有被卡的可能。

字典树Trie

时间复杂度O(n^2)

对于一个字符串构建字典树，那么这颗字典树将会包含所有左端点为\(1\)，右端点\(\in [1...n]\)的所有子串，因此我们枚举作为字符串左端点，依次将\([1...n],[2...n],[3..n],...,[n,n]\)字符串加入同一个字典树。这样结束后，字典树上的所有节点将会包含所有的子串，因此直接输出字典树的节点数即可。

struct Trie
{
    struct Node
    {
        int ch[26];
    } t[maxn + 10];
    int  cnt = 0;
    void init()
    {
        for (int i = 0; i <= cnt; i++)
            memset(t[i].ch, 0, sizeof(t[i].ch));
        cnt = 0;
    }
    void insert(string& s, int l, int r)
    {
        int cur = 0;
        for (int i = l; i <= r;i++){
            int c = s[i] - 'a';
            if(!t[cur].ch[c])
                t[cur].ch[c] = ++cnt;
            cur = t[cur].ch[c];
        }
    }
} t;

void solve(){
    string s;
    cin >> s;
    t.init();
    for (int i = 0; i < s.length();i++)
        t.insert(s, i, s.length() - 1);
    cout << t.cnt << "\n";
}

字典树的做法已经可以通过SPOJ.com - Problem DISUBSTR等题目。

SAM后缀自动机

时间复杂度O(n)

SAM经典模板题，讲解可参考后缀自动机 (SAM) - OI Wiki (oi-wiki.org)

int ans;
namespace SAM {
	struct node {
		int len, link, nxt[26];
	}a[maxn << 1];
	int las = 0, tot = 0;
	inline void init() { a[0].link = -1; }
	inline void insert(int x) {
		int cur = ++tot;
		a[tot].len = a[las].len + 1;
		int p = las;
		while (p != -1 && !a[p].nxt[x]) { a[p].nxt[x] = cur; p = a[p].link; }
		if (p == -1) a[cur].link = 0;
		else {
			int q = a[p].nxt[x];
			if (a[p].len + 1 == a[q].len) a[cur].link = q;
			else {
				int clone = ++tot;
				a[clone] = a[q];
				a[clone].len = a[p].len + 1;
				a[q].link = a[cur].link = clone;
				while (p != -1 && a[p].nxt[x] == q) { a[p].nxt[x] = clone; p = a[p].link; }
			}
		}
		las = cur;
		ans += a[cur].len - a[a[cur].link].len;
	}
}
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	SAM::init();
	for (int i = 0; i < s.length(); i++)
		SAM::insert(s[i] - 'a');
	cout << ans << "\n";
}

该做法可以通过大多数求解不同字串个数的题目。