O(N)

online_Z_algorithm2.cpp

struct online_Z_algorithm {
private:
	string s;
	vector<int> a;
	queue<int> cur;
	vector<bool> deleted;

	vector<vector<int>> delete_memo;
public:
	online_Z_algorithm() { delete_memo.push_back({}); };
	void del(int loc, int len) {
		deleted[loc] = true;
		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({});
		deleted.push_back(false);

		if (len == 1)return;
		if (s[0] == c)cur.push(len - 1);
		else deleted[len - 1] = true;

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