查找连续最长子串，该子串中任何两个字符不能相同，返回子串长度

朴灿烈づ我的快乐病毒、 2022-05-15 03:57 144阅读 0赞

**对于找子字符串问题，有一个通用的方法，尽管有时候可能复杂度比较高，在想不出更好的算法时不失为一种可行的方法。那就是遍历所有的子串。遍历子串的方法，就要用到字符串后缀子串和前缀子串，下面我先简单介绍一下字符串的后缀前缀子串数组。**

以字符串abcde为例，后缀子串有5种，5为字符串长度

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th style="text-align:center;">后缀子串</th> 
   <th style="text-align:center;">长度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center;">e</td> 
   <td style="text-align:center;">1</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">de</td> 
   <td style="text-align:center;">2</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">cde</td> 
   <td style="text-align:center;">3</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">bcde</td> 
   <td style="text-align:center;">4</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">abcde</td> 
   <td style="text-align:center;">5</td> 
  </tr> 
 </tbody> 
</table>

各后缀子串的所有前缀子串为下表

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th style="text-align:center;">后缀子串</th> 
   <th style="text-align:center;">各后缀子串所有的前缀子串</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center;">e</td> 
   <td style="text-align:center;">e</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">de</td> 
   <td style="text-align:center;">d、de</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">cde</td> 
   <td style="text-align:center;">c、cd、cde</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">bcde</td> 
   <td style="text-align:center;">b、bc、bcd、bcde</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">abcde</td> 
   <td style="text-align:center;">a、ab、abc、abcd、abcde</td> 
  </tr> 
 </tbody> 
</table>

由表格可知，**各后缀子串的所有前缀子串一共15种，构成了源字符串abcde的所有子字符串**。那么在此基础上，查找连续重复、连续不重复、第一次重复等等问题都可以迎刃而解了。

下面针对标题，查找连续最长子串，该子串中任何两个字符不能相同，返回子串长度 给出最简单粗暴、但是又最容易吸收理解掌握的实现方法。在此算法上，可以进行各种改进和创新，如何改进和创新读者可以自己尝试。

#include<iostream>
    #include<string>
    using namespace std;
    int main(){
    	string input;
    	while (cin >> input) {
    		int length = input.length();
    		if (length == 0) {
    			cout << 0 << endl;
    			continue;
    		}
    		//存储所有的后缀子串
    		string* sub = new string[length];
    		for (int i = 0; i < length; i++)
    			sub[i] = input.substr(i);
    		int MaxCount = 0;
    		//i为子串长度
    		for (int i = 1; i <= length; i++) {
    			for (int j = 0; j + i <= length; j++) {
    				//后缀子串的所有前缀子串构成所有的子字符串
    				string temp = sub[j].substr(0,i);
    				int k;
    				bool repeat = false;
    				char* hash = new char[256];
    				memset(hash,0,256);
    				for (k = 0; k < temp.length(); k++) {
    					hash[temp[k]]++;
    					if (hash[temp[k]] > 1) {
    						repeat = true;
    						break;
    					}
    				}
    				delete[] hash;
    				if (repeat) 
    					continue;
    				else {
    					MaxCount = i;
    				}
    			}
    		}
    		cout << MaxCount << endl;
    		delete[] sub;
    	}
    }

另有相关问题[连续重复子字符串查找][Link 1]，也可以参考。字符串处理问题是各种面试时最容易考到的问题，望诸君共勉。

[Link 1]: https://blog.csdn.net/u010183728/article/details/80779372