#!/usr/bin/env python # encoding: utf-8 def find(s): array = suffixs(s) array.sort() r = '' max_r = 0 for i in range(len(array)-1): a = array[i] b = array[i+1] lens = min(len(a), len(b)) cnt = 0 for j in range(lens): if a[j] == b[j]: cnt += 1 if max_r < cnt: max_r = cnt r = a[:cnt] return r def suffixs(s): return [s[i:] for i in range(len(s))] if __name__ == '__main__': print find('canffcancd') print find('ttabcftrgabcd')编程珠玑中后缀数组的解法
不能保证正确性,仅仅是记录一下#include<iostream> #include<vector> #include<algorithm> using namespace std; vector<string>init(string s)//生成后缀数组 { vector<string> back; for (int i = 0; i < s.size(); ++i) { string t = ""; t = s.substr(i, s.size() - i); back.push_back(t); } return back; } string mycompare(string a, string b) { string t = ""; for (int i = 0; i < a.size() && i < b.size(); ++i) { if (a[i] == b[i]) t += a[i]; else break; } return t; } string process(vector<string>& ss) { string max_string = ""; sort(ss.begin(), ss.end()); for (int i = 1; i < ss.size(); ++i) { string back=mycompare(ss[i - 1], ss[i]); if (back.size() > max_string.size()) max_string = back; } return max_string; } int main() { vector<string> rr; rr = init("aabc"); /*for (string val : rr) cout << val << endl;*/ cout << process(rr) << endl; return 0; }
const int maxcharnum = 5000000;
bool StrCmp(char *str1,char
*str2)
{
if(strcmp(str1,str2)>=0)
return false;
else
return true;
}
void getsuffixarray(char *str,char
*suffixstr[]) //求取字符串的所有后缀字符串
{
int len = strlen(str);
for(int i = 0 ; i <len;i++)
{
suffixstr[i] =
&str[i];
}
}
int getstrlen(char *str1,char
*str2) //获取字符串相等的长度
{
int len = 0;
while(*str1&&*str2&&*str1++ == *str2++)
len++;
return len;
}
void getmaxrestr(char *str)
{
int len = strlen(str);
int conreslen = 0;
int maxloc
= 0;
int maxlen = 0;
char *suffixstr[maxcharnum];
getsuffixarray(str,suffixstr);
sort(suffixstr,suffixstr+len,StrCmp);//排序