一個字符串中連續出現次數最多的子串【轉】一個字符串中連續出現次數最多的子串【轉】，字符串次數
問題描述：
求一個字符串中連續出現次數最多的子串，子串的長度可以是 1 。
分析問題：
乍一看，好像無處下手。簡單的窮舉效率太低，隨著輸入的文本增長，時間復雜度和空間復雜度就會火箭般竄升至無法接受的地步。
我們需要尋找規律。
假設存在一個長度為 N 的子串 S 出現的次數最多。那麼它具有哪些特點呢？
- S 的任一子串的出現次數不少於 S 的出現次數
- S 中不會出現重復的子串字符
- S 中不會出現重復的字符
- 組成 S 的每一個字符、每一個子串的出現次數都和 S 一樣
“S 中不會出現重復的字符”，“組成 S 的每一個字符、每一個子串的出現次數都和 S 一樣”！ 有了這個結論，問題就簡單了。
算法描述：
找到文本中的出現次數最高的單個字符組成的子串，放入一個隊列中， 從隊列的頭部開始，對結果集中的每一個子串 S 進行處理如此，直至到達隊列尾。
代碼：
#pragma warning(disable : 4786) #include < iostream > #include < string > #include < deque >
#define BUFFSIZE 1024
using std::cout; using std::endl; using std:: string ; using std::deque;
typedef deque < string > strlist;
const string ::size_type npos = - 1 ; const string ignoreChars( " /t/n/r " );
inline bool IgnoreChar( char c){ return (ignoreChars.find(c) != npos); }
/* * 統計字符出現次數 */ unsigned CharSummary( const string & text, unsigned usecount[], int tbllen){ unsigned count, i;
memset(usecount, 0 , tbllen * sizeof (unsigned)); for (i = 0 ;i < text.length();usecount[unsigned(text[i ++ ])] ++ );
for (count = i = 0 ;i < 256 ;i ++ ){ if (IgnoreChar(i)) continue ; if (usecount[i] > count)count = usecount[i]; }
return count; }
/* * 試著增長字符串 */ char TryGrowthString( const string & text, const string & str, int maxcount, unsigned * usecount){ int count; string ::size_type pos; char c = 0 ;
pos = text.find(str); if (pos == npos) return 0 ;
/* 不是出現次數最多的字符 */ c = text[pos + str.length()]; if (usecount[unsigned(c)] < maxcount) return 0 ;
/* 檢查文本中的出現次數 */ for (count = 0 ; pos + str.length() + 1 < text.length();pos += str.length()){ pos = text.find(str, pos); if (pos == npos) break ; if (c != text[pos + str.length()]) return 0 ; }
return c; }
void PrintResult( const strlist & result){ strlist::const_iterator citer;
cout << endl << " The result substrings : " << endl; cout << " ------------------------------------- " << endl; for (citer = result.begin(); citer != result.end(); citer ++ ){ cout << ' " ' <<* citer << ' " ' << endl; } cout << " ------------------------------------- " << endl; cout << " Total : " << result.size() << endl; }
void main( void ){ unsigned usecount[ 256 ]; char buffer[BUFFSIZE], c; unsigned count, i; string text; strlist result;
/* * 從 stdin 讀入文本 */ while ( ! feof(stdin)){ if (fgets(buffer, sizeof (buffer),stdin)) text += buffer; } /* * 統計字符出現次數 */ count = CharSummary(text, usecount, sizeof (usecount) / sizeof ( * usecount)); cout << " Max count : " << count << endl;
if ( 0 == count){ cout << " There is empty string! " << endl << " Bye! " << endl; }
/* * 將出現次數最多的字符作為子串放入結果中 */ for (i = 0 ;i < sizeof (usecount) / sizeof ( * usecount);i ++ ){ if (usecount[i] == count) result.push_back( string ( 1 , char (i))); }
/* * 查找更多的子串 */ for (strlist::iterator iter = result.begin();iter != result.end();iter ++ ){ c = TryGrowthString(text, * iter, count, usecount); if (c) result.push_back( * iter + string ( 1 , c)); }
PrintResult(result); cout << " Bye! " << endl; }
測試輸入：
abcdefg
bcdef
hijklmnopqrstabcdefg
輸出：
Max count :3
The result substrings :
-------------------------------------
"
"
"b"
"c"
"d"
"e"
"f"
"bc"
"cd"
"de"
"ef"
"bcd"
"cde"
"def"
"bcde"
"cdef"
"bcdef"
-------------------------------------
Total : 16
Bye!
轉載地址：http://blog.csdn.net/sayigood/article/details/4413988
一個字符在字符串中連續出現的次數最多的子字符串?算法
public void find(String s){
int i = 0;//字符串下標
int j = 1; //記錄重復數
int max = 1; //記錄最大的重復數
int m = 0; //作為note數組的下標
int note[] = new int[5]; //該數組是記錄輸出最大重復的子字符串的下標
while(i < s.length() - 1){
if(s.charAt(i) == s.charAt(i+1)){
j = j + 1;
}
else{
if(j == max && j != 1){ //該判斷就是為了以防如出現多個最大重復長度的字串，比如aaabbbcc就該有aaa，bbb兩個
m++;
note[m] = i - max +1;
}
if(j > max){
max = j;
note[0] = i - max +1;
for(int n = 1; n < note.length; n++){
note[n] = -1; //出現更大的重復字串則將以前記錄的小標清除
}
}
j = 1;
}
i++;
}
if(max == 1){
System.out.println("所有字符都只單個出現，並無連續");
return;
}
for(int p = 0; p < note.length; p++){
if(note[p] != -1){
System.out.println(s.substring(note[p], note[p]+max));
}
}
}
不明白就請call我啊，呵呵
在一個字符串中連續出現次數最多的字符？？ 用java 怎實現？
public class SearchChar {
public char search(String str){
int lenght=str.length();
int max=0;
int index=0;
int j;
char ch = str.charAt(0);
for(int i=0;i<lenght;){
index=0;
for(j=i+1;j<lenght;j++){
if(str.charAt(i)==str.charAt(j))
index++;
else
break;
}
if(index>max){
max=index;
ch=str.charAt(i);
}
i=j;
}
return ch;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
SearchChar sc=new SearchChar();
char ch=sc.search("ssddfffffffdseeeedsa");
System.out.println(ch);
}
}
