题解【poj2774 Long Long Message】

Description

求两个串的最长连续公共字串

Solution

后缀数组入门题吧

把两个串连在一起，中间加一个分隔符，然后跑一遍后缀数组，得到 height 和 sa

一个 height[i] 对答案有贡献的充要条件是 sa[i] 和 sa[i-1] 分别在两个串中

Code

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 200200;

char s1[N], s2[N], S[N];

int n, tmpn, cnt[N], ans, sa[N], rk[N], height[N];

struct node { int id, x, y; } a[N], b[N];

int main() {

  scanf("%s %s", s1, s2); tmpn = strlen(s1);

  for(int i = 0; s1[i]; i++) S[++n] = s1[i]; S[++n] = '#';

  for(int i = 0; s2[i]; i++) S[++n] = s2[i];

  for(int i = 1; i <= n; i++) cnt[S[i]] = 1;

  for(int i = 0; i <= 128; i++) cnt[i] += cnt[i - 1];

  for(int i = 1; i <= n; i++) rk[i] = cnt[S[i]];

  for(int L = 1; L <= n; L *= 2) {

    for(int i = 1; i <= n; i++)

      a[i].id = i, a[i].x = rk[i], a[i].y = rk[i + L];

    for(int i = 1; i <= n; i++) cnt[i] = 0;

    for(int i = 1; i <= n; i++) cnt[a[i].y]++;

    for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];

    for(int i = 1; i <= n; i++) b[cnt[a[i].y]--] = a[i];

    for(int i = 1; i <= n; i++) cnt[i] = 0;

    for(int i = 1; i <= n; i++) cnt[a[i].x]++;

    for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];

    for(int i = n; i >= 1; i--) a[cnt[b[i].x]--] = b[i];

    for(int i = 1; i <= n; i++)

      if(a[i].x == a[i - 1].x && a[i].y == a[i - 1].y)

        rk[a[i].id] = rk[a[i - 1].id];

      else rk[a[i].id] = rk[a[i - 1].id] + 1;

  } for(int i = 1; i <= n; i++) sa[rk[i]] = i;

  int k = 0;

  for(int i = 1; i <= n; i++) {

    int j = sa[rk[i] - 1]; if(k) k--;

    while(i + k <= n && j + k <= n && S[i + k] == S[j + k]) k++;

    height[rk[i]] = k;

  } for(int i = 1; i <= n; i++)

    if(sa[i] <= tmpn && sa[i - 1] > tmpn ||

       sa[i] > tmpn && sa[i - 1] <= tmpn)

      ans = max(ans, height[i]);

  printf("%d\n", ans);

  return 0;

}