S1 - KMP

class KMP {
	const string s;
	int ar[maxn + 1] {};
	inline void prefunc() {
		ar[0] = -1;
		int i = 0, j = -1;
		while (i < s.length()) {
			if (j == -1 || s[i] == s[j]) ar[++i] = ++j;
			else j = ar[j];
		}
	}
	inline void ntfunc() {
		for (int i = 0; i < s.length(); i++) {
			if (ar[i] != -1 && s[i] == s[ar[i]]) ar[i] = ar[ar[i]];
		}
	}
public:
	explicit KMP(string &p): s(p) { prefunc(), ntfunc(); }
	int solve(string &tar) {
		int ret = 0, i = 0, j = 0;
		while (i < tar.length()) {
			if (j == -1 || tar[i] == s[j]) {
				++i, ++j;
				if (j == s.length()) ++ret, j = ar[j];
			} else j = ar[j];
		}
		return ret;
	}
};