2013.计算机院.Problem D.最小距离查询

川长思鸟来 2023-07-19 12:12 99阅读 0赞

**题目描述**  
给定一个由小写字母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<bits/stdc++.h>
    using namespace std;
    int main() { 
    	int T,m;
    	int pos;
    	char str;
    	scanf("%d",&T);
    	while(T--) { 
    		vector<vector<int> > p(26);
    		char s[100005];
    		scanf("%s",s);
    		int len=strlen(s);
    		for(int i=0; i<len; i++) { 
    			p[s[i]-'a'].push_back(i);
    		}
    		scanf("%d",&m);
    		while(m--) { 
    			char op[10];
    			scanf("%s\n",op);
    			if(strcmp(op,"INSERT")==0) { 
    				scanf("%c",&str);
    				s[len]=	str;
    				s[len+1]='\0';
    				p[str-'a'].push_back(len);
    				len++;
    			}
    			if(strcmp(op,"QUERY")==0) { 
    				int min=100000;
    				scanf("%d",&pos);
    				if(p[s[pos]-'a'].size()==1) { 
    					printf("-1\n");
    				} else { 
    					for(int i=0; i<p[s[pos]-'a'].size(); i++) { 
    						if(abs(p[s[pos]-'a'][i]-pos)<min&&abs(p[s[pos]-'a'][i]-pos)!=0) { 
    							min=abs(p[s[pos]-'a'][i]-pos);
    						}
    					}
    					printf("%d\n",min);
    				}
    			}
    		}
    	}
    }