HDU2594 — 两串的最长相同前后缀

题设

Input

Input consists of two lines. The first line contains s1 and the second line contains s2. You may assume all letters are in lowercase.

Output

Output consists of a single line that contains the longest string that is a prefix of s1 and a suffix of s2, followed by the length of that prefix. If the longest such string is the empty string, then the output should be 0. The lengths of s1 and s2 will be at most 50000.

Sample

Input

clinton
homer
riemann
marjorie

Output

0
rie 3

题解

这道题是作者数据结构课上的一道习题，由于课上刚讲了kmp，再粗略看一下题，可以发现这道题考查的就是kmp。做题时要注意区分模版串和目标串，这里不难看出求前缀的是模版串，求后缀的是目标串。

#include <cstring>
#include <iostream>
using namespace std;
const int N = 50010;

char s1[N], s2[N];
int ne[N];

int main() {
  // freopen("in.txt", "r", stdin);
  cin >> (s1 + 1) >> (s2 + 1);
  int len1 = strlen(s1 + 1);
  int len2 = strlen(s2 + 1);
  
  /* 求next数组 */
  for (int i = 2, j = 0; i <= len1; i++) {
    while (j && s1[i] != s1[j + 1]) j = ne[j];
    if (s1[i] == s1[j + 1]) j++;
    ne[i] = j;
  }

  /* 直接检查到目标串的结尾 */
  int j = 0;
  for (int i = 1; i <= len2; i++) {
    while (j && s2[i] != s1[j + 1]) j = ne[j];
    if (s2[i] == s1[j + 1]) j++;
  }
  if (!j)
    printf("0\n");
  else {
    for (int i = 1; i <= j; i++) printf("%c", s1[i]);
    printf(" %d\n", j);
  }
  return 0;
}

后来想到可以直接将两串头尾相接，对新串求一下next数组即可，只需额外检查一下next数组的下标是否越过连接处，代码量小很多。

#include <cstring>
#include <iostream>
using namespace std;
const int N = 100010;

char s[N];
int ne[N];

int main() {
  // freopen("in.txt", "r", stdin);
  cin >> (s + 1);
  int len1 = strlen(s + 1);
  cin >> (s + len1 + 1);
  int len = strlen(s + 1);
  for (int i = 2, j = 0; i <= len; i++) {
    while (j && s[i] != s[j + 1]) j = ne[j];
    if (s[i] == s[j + 1]) j++;
    ne[i] = j;
  }
  int j = len;
  while (j && j > len1 && j > len - len1) j = ne[j];
  if (!j)
    printf("0\n");
  else {
    for (int i = 1; i <= j; i++) printf("%c", s[i]);
    printf(" %d\n", j);
  }
  return 0;
}