poj2774:对后缀数组的复仇,O(nlog n)做法

2016年5月31日 0 条评论 1.15k 次阅读 0 人点赞

话说上次发了一篇文章..A掉了2774这道水题,但是!用的是O(nlog^2 n)做法,有些不服..

于是本人又研究了一次后缀数组的O(nlog n)做法,终于在昨晚领悟了!特A一题..终于可以教会师弟师妹们这一种数据结构了..哭

直接上代码吧..

Source Code<br />/*<br />Problem: 2774 User: aclolicon<br />Memory: 5212K Time: 610MS<br />Language: G++ Result: Accepted<br />Source Code*/<br />#include&lt;cstdio&gt;<br />#include&lt;iostream&gt;<br />#include&lt;cstring&gt;<br />#define MAXN 200500<br />using namespace std;<br />char s[MAXN], s2[MAXN];<br />int n, len;<br />int sa[MAXN], c[MAXN], t[MAXN], t2[MAXN], rank[MAXN], height[MAXN];<br />void buildsa(){<br /> int *x = t, *y = t2, m = 300;<br /> memset(c, 0, sizeof(c));</p><p> for (int i = 0; i &lt; n; i++) c[x[i] = s[i]]++;<br /> for (int i = 1; i &lt; m; i++) c[i] += c[i - 1];<br /> for (int i = n - 1; i &gt;= 0; i--) sa[--c[x[i]]] = i;<br /> for (int k = 1; k &lt;= n; k *= 2){<br /> int p = 0;<br /> for (int i = n - k; i &lt; n; i++) y[p++] = i;<br /> for (int i = 0; i &lt; n; i++) if (sa[i] &gt;= k) y[p++] = sa[i] - k;<br /> memset(c, 0, sizeof(c));<br /> for (int i = 0; i &lt; n; i++) c[x[y[i]]]++;<br /> for (int i = 1; i &lt; m; i++) c[i] += c[i - 1];<br /> for (int i = n - 1; i &gt;= 0; i--) sa[--c[x[y[i]]]] =y[i];<br /> swap(x, y);<br /> p = 1;<br /> x[sa[0]] = 0;<br /> for (int i = 1; i &lt; n; i++) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] &amp;&amp; y[sa[i - 1] + k] == y[sa[i] + k])? p - 1: p++;<br /> if (p &gt;= n) break;<br /> m = p;<br /> }<br />} </p><p>void geth(){<br /> n = strlen(s);<br /> for (int i = 0; i &lt;= n; i++) rank[sa[i]] = i;<br /> int h = 0;<br /> height[0] = 0;<br /> for (int i = 0; i &lt; n; i++){<br /> int j = sa[rank[i] - 1];<br /> if (h &gt; 0) h--;<br /> for (; j + h &lt; n &amp;&amp; i + h &lt; n; h++){<br /> if (s[j + h] != s[i + h]) break;<br /> }<br /> height[rank[i] - 1] = h;<br /> }<br />}<br />int main(){<br /> while(scanf(&quot;%s&quot;, s) &gt; 0){<br /> scanf(&quot;%s&quot;, s2) &gt; 0;<br /> len = strlen(s2);<br /> n = strlen(s);<br /> if (s2 &gt; s) swap(s, s2);<br /> s[len] = '$';<br /> for (int i = len + 1; i &lt; len + n + 1; i++) s[i] = s2[i - len - 1];<br /> n = strlen(s) + 1;<br /> buildsa();<br /> geth();<br /> int maxh = -1;<br /> for (int i = 0; i &lt; n; i++){<br /> if((sa[i] &lt; len) != (sa[i + 1] &lt; len)){<br /> maxh = max(maxh, height[i]);<br /> }<br /> }<br /> printf(&quot;%d&quot;, maxh);<br /> }<br />}

b-a

这个人太懒什么东西都没留下

文章评论(0)