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


/* 演示調用search函數在str中搜索ptn的過程
 */
typedef Vector<int> (*SearchFunc)(const string&, const string&);
void showSearch(const string& str, const string& ptn, SearchFunc search) {
	cout << "模式匹配的位置: " << endl;

	Vector<int> result = search(str, ptn);
	for (int i = 0; i < result.size(); ++i) {
		cout << " " << result[i];
	}
	cout << "\n位置表示: " << endl;
	cout << str << "\n";
	for (int j = 0, lastpos = 0; j < result.size(); ++j) {
		int offset = result[j] - lastpos - 1;
		for (int k = 0; k < offset; ++k) {
			cout << " ";
		}
		cout << "^";
		lastpos = result[j];
	}
	cout << "\n" << endl;
} // showSearch(const string&, const string&, SearchFunc)


int main() {
	const string ptn = "aabbaab";

	cout << "在主串中搜索所有模式P = \"" << ptn << "\", \n"
		 << "包括重疊及不重疊2種種情況"
		 << endl;
	try {
		cout << "請輸入主串: ";
		string str = getString();

		// 重疊情況下的匹配
		cout << "重疊情況下: " << endl;
		showSearch(str, ptn, KmpSearchAll);
		
		// 無重疊情況下的匹配
		cout << "無重疊情況下: " << endl;
		showSearch(str, ptn, KmpSearchAllNoOverlap);

	} catch (const std::exception& e) {
		cerr << "捕捉到異常!" << endl;
		cerr << e.what() << endl;
		pause();
		return 1;
	}

	pause();
	return 0;

} // main()