BZOJ2105(TLE)

2105.cpp

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ext/rope>
#include <cstring>

using namespace std;
using namespace __gnu_cxx;
char buff0[111111],buff1[111111];
bool check(rope<char> &str, int x,int y, int i){
	//if (x + i > str.size() || y + i > str.size())
	//	return false;
	return str.substr(x, i).compare(str.substr(y, i)) == 0;
}
rope<char> str;
int main(){
	freopen("2105.in", "r", stdin);
	int n, q;
	scanf("%d%d", &n, &q);
	scanf("%s", buff0);
	str.append(buff0);
	while (q--) {
		scanf("%s", buff0);
		if (buff0[0] == 'L') {
			int a,b;scanf("%d%d", &a, &b);a--, b--;
			int L = 1, R = min(str.size() - a, str.size() - b) + 1;
			if (str[a] != str[b]){
				puts("0");
				continue ;
			}
			for (int mid = (L + R) >> 1; L < R; (check(str,a,b,mid))?(L = mid + 1):(R = mid)) {
				mid = (L + R) >> 1;
			}
			printf("%d\n", L - 1);
		} else if (buff0[0] == 'A') {
			int x;
			scanf("%d%s", &x, buff1);x--;
			int len = strlen(buff1);
			str.insert(x, buff1, len);
		} else if (buff0[0] == 'C') {
			int a, b;
			scanf("%d%d%s", &a, &b, buff1);a--;b--;int len = strlen(buff1);
			str.replace(a, b - a + 1, buff1, len);
		} else if (buff0[0] == 'D') {
			int a, b;
			scanf("%d%d", &a, &b);a--,b--;
			str.erase(a, b - a + 1);
		}
	}
}