找出連續同字母排列最長字串

2016-01-09

2325
0
C++

當使用者輸入一個字串時，此程式可以自動回傳出該字串當中連續同字母排列的最長字串。

本文以C++實作執行。

以下是實作"找出連續同字母排列最長字串"實作程式碼:

string longSubstring(string);

string longSubstring(string s)
{
	char indexMax = s[0] ;//存最大的值
	int countMax = 1;//存最大的次數
	char indexTemp ;//存比較的值
	int countTemp = 1;//存比較的次數
	int temp = 0;//存第二個不一樣字元的開始位置
	int finalend;//所需子字串的最末位置


	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == s[i + 1])//如果下個字元和目前字元相等
		{
			countMax++;
		}
		if (s[i] != s[i + 1])//如果下個字元和目前字元不相等
		{
			indexTemp = s[i + 1];
			temp=i + 1;//紀錄第一個字串之後的下一個字元位置
			break;
		}
	}


	for (; temp < s.length(); temp++)
	{
			
		if (s[temp] == s[temp + 1])//下個字元和目前字元一樣的話 計數加一
		{
			countTemp++;
		}


		if (s[temp] != s[temp + 1])
		{
			if (countTemp >= countMax)//目前計數子字串大於最大子字串時
			{
				countMax = countTemp;
				indexMax = indexTemp;

				if (temp + 1 <= s.length())//排除最後一個字串的下個字元為空的狀況
				{
					indexTemp =s[temp + 1];
					countTemp = 1;
					finalend = temp- countMax+1;//紀錄相同字串的第一個位置
				}
			}
		}	

	}

	return s.substr(finalend,countMax);//回傳字串中最長子字串
}

當中的 substr是string當中的函式，其用法如下:

str.substr(startpos, length);

其中參數startpos是起始字串的，參數length是"從startpos 開始"取的字串長度（包括 startpos ）。

完整程式碼如下:

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

string longSubstring(string);

int main() {

	string s;


	cout << "請輸入一個字串:";
	cin>>s;
	
	cout << "原始字串:" << s << endl;
	cout<<"最長子字串:"<<longSubstring(s)<<endl;

	system("pause");
	return 0;
}

string longSubstring(string s)
{
	char indexMax = s[0] ;//存最大的值
	int countMax = 1;//存最大的次數
	char indexTemp ;//存比較的值
	int countTemp = 1;//存比較的次數
	int temp = 0;//存第二個不一樣字元的開始位置
	int finalend;//所需子字串的最末位置


	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == s[i + 1])//如果下個字元和目前字元相等
		{
			countMax++;
		}
		if (s[i] != s[i + 1])//如果下個字元和目前字元不相等
		{
			indexTemp = s[i + 1];
			temp=i + 1;//紀錄第一個字串之後的下一個字元位置
			break;
		}
	}


	for (; temp < s.length(); temp++)
	{
			
		if (s[temp] == s[temp + 1])//下個字元和目前字元一樣的話 計數加一
		{
			countTemp++;
		}


		if (s[temp] != s[temp + 1])
		{
			if (countTemp >= countMax)//目前計數子字串大於最大子字串時
			{
				countMax = countTemp;
				indexMax = indexTemp;

				if (temp + 1 <= s.length())//排除最後一個字串的下個字元為空的狀況
				{
					indexTemp =s[temp + 1];
					countTemp = 1;
					finalend = temp- countMax+1;//紀錄相同字串的第一個位置
				}
			}
		}	

	}

	return s.substr(finalend,countMax);//回傳字串中最長子字串
}

執行結果如下:

有夢最美築夢踏實

活在當下認真過每一天

我是阿夢也是Ace

回首頁