#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:干草堆應該是返回字符串在另一個字符串首次出現的位置，如果沒有返回-1.采用后綴樹應該是可以做的：后綴樹主要是產生n個后綴子串：分別是從第1個字符到第n個字符，第2個字符到第n個字符，...,第n個字符到第n個字符。【1】然后對每個后綴字符串，建立后綴樹：需要一個位置數組記錄從根節點到當前結點對應字符的子串出現的各個位置，返回的第一個位置就是。另外一種方式來查找最長重復子串：采用后綴數組的形式，比如字符串為"abcab"，仍然采用【1】中方式生成的后綴子串分別為:abcab,bcab,cab,ab,b對應子串起始位置為:0    ,1   ,2  ,3 ,4然后排序，得到:ab,abcab,b,bcab,cab發現：采用后綴數組不行，只能用后綴樹來做，時間復雜度為O(n)。后綴結點包含：當前字符值，孩子結點，位置數組(26個字母組成，至少需要26個孩子結點)后綴樹包含：后綴根節點，初始化存放字符串的函數，生成后綴子串，能夠查找的函數，釋放空間的函數輸入:chaoma machaoma oachaoma ""chaoaom ao輸出:4-1-12關鍵：1直接采用簡單的方法：遍歷主串所有可能的起始位置，然后查找與模式串是否相同2 后綴結點中，不是采用指針數組，而是采用<字符，指針>方式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){}	//根據給定的后綴子串，依次尋找到后綴子串中的下一個字符，然后如果該字符對應的結點沒有生成就生成該結點，并記錄其位置; 其實這里傳入的肯定是根節點	void generateSuffix(string& str  , int pos)	{		_positions.push_back(pos);//易錯，即使是空字符串，也需要保存位置，否則最后遞歸查找的是空串		if(str.empty() || pos < 0)		{			return;		}		char ch = str.at(0);		//如果當前字符對應的孩子結點沒有，就新建該結點		if(_childs.find(ch) == _childs.end())		{			SuffixNode* node = new SuffixNode(ch);			_childs[ch] = node;		}		string remainder = str.substr(1);		//以當前新建的結點作為根節點繼續處理		_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，因為主串中起始字符位置不可能超過該位置		for(i = 0 ; i < len1 - len2 + 1; i++)		{			for(j = 0 ; j < len2 ;)			{				//遍歷到發現某個字符不等，直接換另一個起始字符				if(haystack.at(i + j) != needle.at(j))				{					break;				}				//找到起始相同的字符，判斷后續是否相同				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;}