[CF 533E] Correcting Mistakes

作法：

假設原字串為 X ，並且遺漏掉的兩個位子分別是 X[ a ] 和 X[ b ] ，其中 a < b ，那麼可以得到：S[ i ] = T[ i ] ，對於所有的 i < a 或 i >= b ，並且對於 a ~ b 之間的區間，會變成兩個字串位移一個，也就是如果設 S 是漏掉 X[ a ] 的字串， T 是漏掉 X[ b ] 的字串，那麼 S[ i ] = T[ i + 1 ] ，其中 a <= i < b - 1 。因此只要先找到兩個字串從左邊開始比對的第一個不一樣的點，還有從右邊開始比對的第一個不一樣的點，把中間的部份切下來，看把 S 往左移一格或往右移一格會不會和 T 一模一樣就好了。

這題我在賽中 hack 到了3個人，用的測資是： 3 aba bab ，答案是 2 ，不少人都以為如果兩個字串不一樣的位置太多，那麼答案一定 <= 1 。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
char s[maxn],t[maxn] ;
main()
{
    int n ; scanf("%d%s%s",&n,s+1,t+1) ;
    int x=-1 , y=-1 ;
    for(int i=1;i<=n;i++) if(s[i]!=t[i])
        {x=i ; break ;}
    for(int i=n;i>=1;i--) if(s[i]!=t[i])
        {y=i ; break ;}
 
    int ans=0 , i ;
    for(i=x;i<y;i++) if(s[i]!=t[i+1]) break ;
    if(i==y) ans++ ;
    for(i=x;i<y;i++) if(t[i]!=s[i+1]) break ;
    if(i==y) ans++ ;
 
    printf("%d\n",ans) ;
}