算法分析：
算法一：每次查询直接调用query，并且左右都分别遍历到尽头。超时
算法二：优化了“左右分别遍历到尽头”的算法，采取了从index开始向两侧同时遍历，第一次找到相同值就返回。依然超时
算法三：在各种优化了输入输出依然超时后，终于意识到问题的本质——m具有可怕的最大值，也就是说将要面对的是海量的查询次数。
每次查询都要重新调用query的话会造成时间的严重浪费。于是想到使用空间换时间，设置一个dist[]，在查询之前先做一次预处理初始化dist。
然后在以后每次INSERT之后都再从尾至前遍历一遍，更新一下dist[]，在面对海量的查询时可以节省下大量的时间。
Debug记录：
1.依然是没有做好scanf中 %s与%c的过渡
2.scanf时忘写&了
题目描述
给定一个由小写字母a到z组成的字符串S，其中第i个字符为S[i]（下标从0开始）。你需要完成下面两个操作：
INSERT c
其中c是一个待输入的字符。你需要在字符串的末尾添加这个字符。保证输入的字符同样是a到z之间的一个小写字母。
QUERY x
其中x是一个输入的整数下标。对于这个询问，你需要回答在S当中和S[x]相等且与x最近的距离。输入保证x在当前字符串中合法。
例如S = “abcaba”，如果我们操作：
INSERT a
则在S的末端加一个字符a，S变成”abcabaa”。
接下来操作
QUERY 0
由于S[0] = a，在S中出现的离他最近的a在下标为3的位置上，距离为3 - 0 = 3。因此应当输出3。
接下来，如果
QUERY 4
S[4] = b，S中离它最近的b出现在下标为1处，距离为4 - 1 = 3。同样应当输出3。
给定初始字符串S和若干操作，对于每个QUERY，你需要求出相应的距离。
HINT 由于输入数据较大，C/C++中推荐使用scanf进行读入以获得更快的读入速度。同时请注意算法复杂度。
输入格式
输入的第一行是一个正整数T(T≤20)，表示测试数据的组数。
每组输入数据的第一行是一个初始串S。第二行是一个正整数m(1≤m≤100000)，表示总共操作的数量。接下来m行，每行表示一个操作。操作的格式如上所述。
数据保证在任何情况下，S的长度不会超过100000。
输出格式
对于每个QUERY，输出所求的最小距离。如果S中其它位置都不存在和它相同的字符，输出-1。
输入样例
2
axb
3
INSERT a
QUERY 0
QUERY 1
explore
3
INSERT r
QUERY 7
QUERY 1
输出样例
3
-1
2
-1
#include <cstdio>
#include <iostream>
#include <cstring>
#define MAXSIZE 100010
using namespace std;
char str[MAXSIZE];
int dist[MAXSIZE];//0±íʾδ²éѯ£¬-1±íʾ²»´æÔÚ
int len;
void insert(char c){
int newDist;
str[len]=c;
str[len+]='\0';
len++;
int i;
bool haveFind=false; //±ê¼ÇÊÇ·ñÕÒµ½ÐÂÔªËصÄ×î¶Ì¾àÀë
for (i=len-;i>=;i--){//´ÓºóÍùÇ°±éÀú¸üÐÂdistµÄÖµ
if (str[i]==str[len-]){
newDist=len--i;
if(haveFind==false){
dist[len-]=newDist;
haveFind=true;
}
if (newDist<dist[i]||dist[i]==-){
dist[i]=newDist;
}
}
}
if (haveFind==false)
dist[len-]=-;
}
int query(int index){
int lIndex=index-,rIndex=index+;
while (lIndex>=||rIndex<len){
if (lIndex>=&&str[lIndex]==str[index])
return dist[index]=index-lIndex;
if (rIndex<len&&str[rIndex]==str[index])
return dist[index]=rIndex-index;
lIndex--;rIndex++;
}
return dist[index]=-;
// while (lIndex>=0&&str[lIndex]!=str[index])
// lIndex--;
// while (str[rIndex]!='\0'&&str[rIndex]!=str[index])
// rIndex++;
// int lDis=abs(index-lIndex);
// int rDis=abs(rIndex-index);
// int minDis;
//
// if (lIndex==-1){
// if (str[rIndex]=='\0')
// minDis=-1;
// else
// minDis=rDis;
// }
// else if (str[rIndex]=='\0'){
// minDis=lDis;
// }
// else{
// minDis=lDis<rDis?lDis:rDis;
// }
// return minDis;
}
int main(){
int t,m;
char c;
int index;
char operation[];
scanf("%d",&t);
//preprocess
while (t--){
//initiate
scanf("%s",str);
len=strlen(str);
for (int i=;i<len;i++){
dist[len]=;
}
scanf("%d",&m);
//preprocess
for (int i=;i<len;i++){
query(i);
}
//operate
for (int i=;i<m;i++){
scanf("%s",operation);
if (operation[]=='I'){
getchar();
scanf("%c",&c);/*bug*/
insert(c);
//**debug**
// cout<<str<<endl;
// return true;
//********
}
else if (operation[]=='Q'){
scanf("%d",&index);/*bug*/
if (dist[index]==)
query(index);
printf("%d\n",dist[index]);
}
}
}
return true;
}