按照题解的说法不论是s.compare还是重载的==,大概都是O(n)的时间复杂度,当T,n和q比较大时非常容易超时,而且我就改了一个字符,没必要把所有位置都再比较一次吧?
思路大概是第一次出现两个字符串时统计不相同位置的数量cnt,如果cnt为0那么相同,否则不相同。
其后每一次修改,需要判断四种情况(其实就两种)
改之前s[p-1]和t[p-1]相同,改之后s[p-1]和t[p-1]相同,那么cnt不变(忽略不写)
改之前s[p-1]和t[p-1]相同,改之后s[p-1]和t[p-1]不相同,那么cnt++(不相同位置的数量增加一个)
改之前s[p-1]和t[p-1]不相同,改之后s[p-1]和t[p-1]不相同,那么cnt不变(忽略不写)
改之前s[p-1]和t[p-1]不相同,改之后s[p-1]和t[p-1]相同,那么cnt--(不相同位置的数量减少一个)
之后再判断cnt就可以啦,不必要再判断n次,以下给出部分AC代码
#include<iostream>
#define endl '\n'
using namespace std;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
return 0;
}