[筆試題]查找一個字元串在另一個字元串中的連接配接次序

題目描述

輸入兩個字元串，比如abdbcc和abc，輸出第二個字元在第一個字元中的連接配接次序。即輸出125，126，145，146.

思路

思路1

先找到第二個字元串中各個字元在第一個字元串中分别出現的位置，利用位置構造多叉樹（構造規則為位元組點必須小于父節點）。周遊構造完成的多叉樹即為相應的組合。本例為

      1

  2      4

5  6  5  6

思路2

利用遞歸。先找出第一個字元出現的位置，後面的遞歸處理。遞歸出口為找到最後未找到結果或者找到結果（出現次數的和第二個字元串長度相同）。

代碼

遞歸 代碼的實作：

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

void printArr(char* srcArr, char* subArr, int* result, int srcStart, int srcEnd, int subStart, int subEnd, int resultStart)
{
	cout << "\tprintArr(" << srcStart << "," << srcEnd << "," << srcStart <<"," << subEnd <<"," << resultStart <<")." << endl;
	if(srcEnd - srcStart < subEnd - subStart)
	{
		return ;
	}

	if(resultStart == subEnd) //已經找到一個結果,輸出
	{
		for(int i = 0; i < resultStart; i++)
			cout << result[i];
		cout << endl;
	}

	for(int i = srcStart; i < srcEnd; i++)
		for(int j = subStart; j < subEnd; j++)
			if(srcArr[i] == subArr[j])//找到第一個相同的字元,遞歸處理後面的
			{
				result[resultStart] = i+1;
				printArr(srcArr, subArr, result, i+1, srcEnd, j+1, subEnd, resultStart+1);
			}
}

void findSubIndex(char* srcArr, char* subArr)
{
	int srcSize = strlen(srcArr);
	int subSize = strlen(subArr);
	if(srcSize < subSize)
	{
		cerr << "Don't exist." << endl;
		return;
	}
	int *result = new int[subSize]();
	if(result == NULL)
	{
		cerr << "Error allocate memory." << endl;
		return ;
	}
	printArr(srcArr, subArr, result, 0, srcSize, 0, subSize, 0);
}

int main(int argc,char *argv[])
{
	char srcArr[]="abdbcc";
	char subArr[]="abc";
	findSubIndex(srcArr, subArr);
	return 0;
}