online Z algorithm

online_Z_algorithm.cpp

struct online_Z_algorithm {
private:
	string s;
	vector<int> a;
	set<int> cur;

	vector<vector<int>> delete_memo;
public:
	online_Z_algorithm() { delete_memo.push_back({}); };
	void del(int loc, int len) {
		cur.erase(loc);
		delete_memo[len].push_back(loc);
		a[loc] = len - loc - 1;
	}
	//末尾に文字cを挿入する
	void add(char c) {
		s.push_back(c);
		int len = s.size();
		a.push_back(0);
		delete_memo.push_back({});

		if (len == 1)return;
		if (s[0] == c)cur.insert(len - 1);

		while (cur.size()) {
			int left = *cur.begin();
			if (s[len - left - 1] == s.back())break;
			else {
				del(left, len);
			}
		}
		if (cur.size()) {
			int pre = *cur.begin();
			for (int past : delete_memo[len-pre]) {
				del(past + pre,len);
			}
		}
	}
	//loc番目以降の文字列と元の文字列の最長共通接頭辞を求める
	int query(int loc) {
		if (loc == 0)return s.size();
		if (cur.count(loc))return s.size() - loc;
		else return a[loc];
	}
};