bzoj3172: [Tjoi2013]单词

xiaoxiao2021-02-28  13

题面在这里

题意:

给n个单词,问每个单词在所有单词中出现了多少次。

做法:

后缀数组。(ac自动机也可以qwq) 首先把所有串用不同的字符拼接起来,跑大串的sa。 然后对于每一个单词,假设它的长度为len,暴力找到h[i]>=len的最左边和最右边的位置l,r,然后这个单词出现的次数就是这一段的长度r-(l-1)+1。 (其实暴力应该是水过的?qaq,正解大概搞个二分什么的就行。。反正暴力能过qaq。。1000+ms)

代码:

/************************************************************* Problem: bzoj 3172 [Tjoi2013]单词 User: fengyuan Language: C++ Result: Accepted Time: 1392 ms Memory: 50120 kb Submit_Time: 2018-01-24 08:46:04 *************************************************************/ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cctype> #include<cstdlib> #include<cmath> using namespace std; typedef long long ll; const int N = 2000000; int n, m, all; int rk[N], tp[N], sa[N], h[N], len[210], tong[N], pos[210], s[N]; char str[N]; inline void ssort() { for(int i = 0; i <= all; i ++) tong[i] = 0; for(int i = 1; i <= n; i ++) tong[rk[tp[i]]] ++; for(int i = 1; i <= all; i ++) tong[i] += tong[i-1]; for(int i = n; i >= 1; i --) sa[tong[rk[tp[i]]] --] = tp[i]; } inline void get_sa() { for(int i = 1; i <= n; i ++) rk[i] = s[i], tp[i] = i; all = 500; ssort(); all = 1; int w = 1; while(all < n) { int t = 0; for(int i = n-w+1; i <= n; i ++) tp[++ t] = i; for(int i = 1; i <= n; i ++) if(sa[i] > w) tp[++ t] = sa[i]-w; ssort(); for(int i = 1; i <= n; i ++) tp[i] = rk[i]; rk[sa[1]] = all = 1; for(int i = 2; i <= n; i ++) rk[sa[i]] = (tp[sa[i]] == tp[sa[i-1]] && tp[sa[i]+w] == tp[sa[i-1]+w])?all:++ all; w <<= 1; } int k = 0; for(int i = 1; i <= n; i ++) { if(k) k --; int j = sa[rk[i]-1]; for(; i+k <= n && j+k <= n && s[i+k] == s[j+k]; k ++); h[rk[i]] = k; } } int main() { scanf("%d", &m); for(int i = 1; i <= m; i ++) { scanf("%s", str); len[i] = strlen(str); pos[i] = n+1; for(int j = 0; j < len[i]; j ++) s[++ n] = str[j]; s[++ n] = 'z'+i; } get_sa(); for(int i = 1; i <= m; i ++) { int x = rk[pos[i]], j, lft, rgt; j = x; while(j && h[j] >= len[i]) j --; lft = j+1; j = x+1; while(j <= n && h[j] >= len[i]) j ++; rgt = j-1; printf("%d\n", rgt-(lft-1)+1); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-1450116.html

最新回复(0)