Delete it

時間限制：2000?ms ?|? 內存限制：65535?KB 難度：2 描述

克林在打一行字母時總是會打多一個字符，比如想打”july”時會打成”juuly”,這樣他需要刪掉其中一個’u’。

克林想知道他可以刪掉哪個位置的字符就可以變成他真正想打的一行字母。

輸入

第一行一個整數:T (測試個數)

每個測試
輸入兩行，兩個字符串（全是小寫字母）
串長為 1 到 1000000
第一個串長度剛好比第二個的長度大一

輸出

每個測試數據：
第一行輸出可以刪除的位置個數 P
如果P > 0 第二行輸出可以刪除的位置（小到大，空格隔開，位置從1開始算）

樣例輸入

3 juuly july abc zz aa a

樣例輸出

2 2 3 0 2 1 2

直接循環比較字符，不會超時，代碼注釋中寫思路

AC代碼：

#include <stdio.h> #include <string.h> char a[1000003], b[1000003]; int c[1000003];//存可以刪的字符下標 int main() {int T, i, j, t;scanf("%d", &T);while(T--) {char x = 0, fag = 0;scanf("%s%s", a+1, b+1);//字符串從a+1開始放主要是不想在后面存下標時(或輸出每個下標時)每次都去+1 //個人感覺這樣可以降低一定的時間復雜度 i = 1;int L = strlen(b+1);while(a[i] == b[i]) i++;j = i+1;t = i;while(a[j] == b[i] && i <= L) {//因為輸入時是a+1,所以這里i<=L i++;j++; }if(i > L) fag = 1;j = 0;if(fag) {//fag為0不執行 //因為fag為0意味著沒有可刪除的字符讓a串變成b串 c[j++] = t;x = a[t--];}while(a[t] == x && t > 0) c[j++] = t--;//回到不相同的地方往前看有幾個連續與該多余字符相同的 printf("%d\n", j);while(j--) printf("%d ", c[j]);if(fag == 1) printf("\n");//fag為0不輸出換行//不過這題有沒有都能過 }return 0; }

QQ:754912298

歡迎交流

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的nyoj359Delete it的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。