求串s中出现的第一个最长重复子串及其位置

// --------------------------------------
// 求串S中出现的第一个最长重复字串及其位置
// ---------------------------------------

#include <iostream>
#include <string>
using namespace std;

// KMP算法中，next数组所存的是，在第j个字符前存在一个长度为next[j]-1的重复子串
// 重复子串：SubString(S,i,len) = SubString(S,j,len)

void GetNext(string s, int next[], int length) {
 int i = 0;
 int j = -1;
 next[0] = -1;
 while (i < length) {
  if (j == -1 || s[i] == s[j]) {
   i++;
   j++;
   next[i] = j;
  }
  else
   j = next[j];
 }
}

int MaxNext(int a[], int length) {
 int max = -1;
 for (int i = 0; i < length; i++) {
  max = max < a[i] ? a[i] : max;
 }
 return max;
}

int MaxRepSubString(string s,int &l) {
 l = 0;
 int pos = -1,i;
 int max = -1;
 int length = s.length();
 for (i = 0; i < length - 1; i++) {
  string tmp(s, i, length - i);
  int *next = new int[tmp.length()];
  GetNext(tmp, next, tmp.length());
  max = MaxNext(next, tmp.length());
  if (tmp[tmp.length() - 1] == tmp[max]) {
   max = max + 1;
  }
  if (l < max) {
   l = max;
   pos = i;
  }
 }
 return pos;
}

int main() {
 string s = "abaabaa";
 int l;
 int pos = MaxRepSubString(s,l);
 if (pos == -1)
  cout << "不存在" << endl;
 else
 {
  string res(s, pos, l);
  cout << res << endl;
 }

 system("pause");
 return 0;
}

求串s中出现的第一个最长重复子串及其位置

原文：http://www.cnblogs.com/codingtao/p/6430951.html