0w1

CFR 533 E. Correcting Mistakes ( Ad hoc )

Problem - E - Codeforces

題意:
給你長度 N,以及長度 N 的兩個相異字串 S 和 T。求有多少可能的字串 W,使得從 W 刪去一個字符可以成為 S,也能成為 T。

資料規模:
The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T.
The second line contains word S.
The third line contains word T.
Words S and T consist of lowercase English letters. It is guaranteed that S and T are distinct words.
TL: 2000 ms
ML: 256 MB

解法:
一開始用 hash 暴力做,枚舉塞的字母,枚舉塞的位子,因為要至少做兩個 hash ( 不然幾乎 100% 會碰撞 ),所以最大 case 貌似要 3000 ms,可惜。考慮 W 可能的長相。大概是 W = seq1 + x + seq2 + y + seq3 吧。seq1, seq2, seq3 可以是任意字串 ( 可為空 ),然後消去 x 變成 S 或 T,消去 y 也同理。所以我們先找這個 S 和 T 的共通前綴和後綴 seq1, seq3,並刪去。現在 S 可為 x + seq2 或 seq2 + y,T 也同理。因為保證輸入 S != T,所以只有兩種可能,暴力比較就行。

時間 / 空間複雜度:
O( N )

int N;
string S;
string T;

void init(){
  cin >> N;
  cin >> S;
  cin >> T;
}

void solve(){
  int lcp;
  for( lcp = 0; S[ lcp ] == T[ lcp ]; ++lcp ) ;
  int lcs;
  for( lcs = N - 1; S[ lcs ] == T[ lcs ]; --lcs ) ;
  ++lcs;
  string s = S.substr( lcp, lcs - lcp );
  string t = T.substr( lcp, lcs - lcp );
  int ans = ( s.substr( 1 ) == t.substr( 0, t.size() - 1 ) ) + ( s.substr( 0, s.size() - 1 ) == t.substr( 1 ) );
  cout << ans << endl;
}