#include <iostream>#include <stdio.h>#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <map>using namespace std;/*問題: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)該是返回字符串在另一個字符串首次出現(xiàn)的位置，如果沒有返回-1.采用后綴樹應(yīng)該是可以做的：后綴樹主要是產(chǎn)生n個后綴子串：分別是從第1個字符到第n個字符，第2個字符到第n個字符，...,第n個字符到第n個字符。【1】然后對每個后綴字符串，建立后綴樹：需要一個位置數(shù)組記錄從根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)對應(yīng)字符的子串出現(xiàn)的各個位置，返回的第一個位置就是。另外一種方式來查找最長重復(fù)子串：采用后綴數(shù)組的形式，比如字符串為"abcab"，仍然采用【1】中方式生成的后綴子串分別為:abcab,bcab,cab,ab,b對應(yīng)子串起始位置為:0    ,1   ,2  ,3 ,4然后排序，得到:ab,abcab,b,bcab,cab發(fā)現(xiàn)：采用后綴數(shù)組不行，只能用后綴樹來做，時間復(fù)雜度為O(n)。后綴結(jié)點(diǎn)包含：當(dāng)前字符值，孩子結(jié)點(diǎn)，位置數(shù)組(26個字母組成，至少需要26個孩子結(jié)點(diǎn))后綴樹包含：后綴根節(jié)點(diǎn)，初始化存放字符串的函數(shù)，生成后綴子串，能夠查找的函數(shù)，釋放空間的函數(shù)輸入:chaoma machaoma oachaoma ""chaoaom ao輸出:4-1-12關(guān)鍵：1直接采用簡單的方法：遍歷主串所有可能的起始位置，然后查找與模式串是否相同2 后綴結(jié)點(diǎn)中，不是采用指針數(shù)組，而是采用<字符，指針>方式3 后綴樹中生成采用遞歸方式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ù)給定的后綴子串，依次尋找到后綴子串中的下一個字符，然后如果該字符對應(yīng)的結(jié)點(diǎn)沒有生成就生成該結(jié)點(diǎn)，并記錄其位置; 其實(shí)這里傳入的肯定是根節(jié)點(diǎn)	void generateSuffix(string& str  , int pos)	{		_positions.push_back(pos);//易錯，即使是空字符串，也需要保存位置，否則最后遞歸查找的是空串		if(str.empty() || pos < 0)		{			return;		}		char ch = str.at(0);		//如果當(dāng)前字符對應(yīng)的孩子結(jié)點(diǎn)沒有，就新建該結(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;		//只需要匹配到主串長度 - 模式串長度 + 1，因?yàn)橹鞔衅鹗甲址恢貌豢赡艹^該位置		for(i = 0 ; i < len1 - len2 + 1; i++)		{			for(j = 0 ; j < len2 ;)			{				//遍歷到發(fā)現(xiàn)某個字符不等，直接換另一個起始字符				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++;					}					//如果此時j等于len2，說明找到，退出					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;}