#include <iostream>#include <stdio.h>#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <map>using namespace std;/*問(wèn)題:Implement strStr().Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.分析：needle：針haystack:干草堆應(yīng)該是返回字符串在另一個(gè)字符串首次出現(xiàn)的位置，如果沒(méi)有返回-1.采用后綴樹(shù)應(yīng)該是可以做的：后綴樹(shù)主要是產(chǎn)生n個(gè)后綴子串：分別是從第1個(gè)字符到第n個(gè)字符，第2個(gè)字符到第n個(gè)字符，...,第n個(gè)字符到第n個(gè)字符?！?】然后對(duì)每個(gè)后綴字符串，建立后綴樹(shù)：需要一個(gè)位置數(shù)組記錄從根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)字符的子串出現(xiàn)的各個(gè)位置，返回的第一個(gè)位置就是。另外一種方式來(lái)查找最長(zhǎng)重復(fù)子串：采用后綴數(shù)組的形式，比如字符串為"abcab"，仍然采用【1】中方式生成的后綴子串分別為:abcab,bcab,cab,ab,b對(duì)應(yīng)子串起始位置為:0    ,1   ,2  ,3 ,4然后排序，得到:ab,abcab,b,bcab,cab發(fā)現(xiàn)：采用后綴數(shù)組不行，只能用后綴樹(shù)來(lái)做，時(shí)間復(fù)雜度為O(n)。后綴結(jié)點(diǎn)包含：當(dāng)前字符值，孩子結(jié)點(diǎn)，位置數(shù)組(26個(gè)字母組成，至少需要26個(gè)孩子結(jié)點(diǎn))后綴樹(shù)包含：后綴根節(jié)點(diǎn)，初始化存放字符串的函數(shù)，生成后綴子串，能夠查找的函數(shù)，釋放空間的函數(shù)輸入:chaoma machaoma oachaoma ""chaoaom ao輸出:4-1-12關(guān)鍵：1直接采用簡(jiǎn)單的方法：遍歷主串所有可能的起始位置，然后查找與模式串是否相同2 后綴結(jié)點(diǎn)中，不是采用指針數(shù)組，而是采用<字符，指針>方式3 后綴樹(shù)中生成采用遞歸方式4 class SuffixNode{public:	char _value;	//SuffixNode* _childs[CHILD_SIZE];//0~25是'a'~'z',26~51是'A'到'Z' = 	map<char , SuffixNode*> _childs;	vector<int> _positions;public:	SuffixNode(){}	SuffixNode(char value):_value(value){}	//根據(jù)給定的后綴子串，依次尋找到后綴子串中的下一個(gè)字符，然后如果該字符對(duì)應(yīng)的結(jié)點(diǎn)沒(méi)有生成就生成該結(jié)點(diǎn)，并記錄其位置; 其實(shí)這里傳入的肯定是根節(jié)點(diǎn)	void generateSuffix(string& str  , int pos)	{		_positions.push_back(pos);//易錯(cuò)，即使是空字符串，也需要保存位置，否則最后遞歸查找的是空串		if(str.empty() || pos < 0)		{			return;		}		char ch = str.at(0);		//如果當(dāng)前字符對(duì)應(yīng)的孩子結(jié)點(diǎn)沒(méi)有，就新建該結(jié)點(diǎn)		if(_childs.find(ch) == _childs.end())		{			SuffixNode* node = new SuffixNode(ch);			_childs[ch] = node;		}		string remainder = str.substr(1);		//以當(dāng)前新建的結(jié)點(diǎn)作為根節(jié)點(diǎn)繼續(xù)處理		_childs[ch]->generateSuffix(remainder , pos);	}*/class Solution {public:    int strStr(string haystack, string needle) {		//如果都為空，返回0		if(haystack.empty() && needle.empty())		{			return 0;		}		//模式串為空，返回0		else if(needle.empty())		{			return 0;		}		//主串為空，返回-1，查找不到		else if(haystack.empty())		{			return -1;		}		int len1 = haystack.length();		int len2 = needle.length();		int i;		int j;		//只需要匹配到主串長(zhǎng)度 - 模式串長(zhǎng)度 + 1，因?yàn)橹鞔衅鹗甲址恢貌豢赡艹^(guò)該位置		for(i = 0 ; i < len1 - len2 + 1; i++)		{			for(j = 0 ; j < len2 ;)			{				//遍歷到發(fā)現(xiàn)某個(gè)字符不等，直接換另一個(gè)起始字符				if(haystack.at(i + j) != needle.at(j))				{					break;				}				//找到起始相同的字符，判斷后續(xù)是否相同				else				{					int tempPos = i + j;					while(j < len2 && haystack.at(i + j) == needle.at(j))					{						j++;					}					//如果此時(shí)j等于len2，說(shuō)明找到，退出					if(j == len2)					{						return tempPos;					}				}			}		}		return -1;    }};void PRocess(){	string haystack;	string needle;	Solution solution;	while(cin >> haystack >> needle)	{		int pos = solution.strStr(haystack ,needle);		cout << pos << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}