TIOJ 1502

2qbingxuan

2024-12-18

Every time you’re next to me

https://tioj.ck.tp.edu.tw/problems/1502

Description

有一個字串 $T$ 和一個 pattern $P$，其中 $P$ 有一些字元是 *，* 可以匹配一個或以上的任意字元，且 * 不會連續出現，請問 $T$ 裡面有沒有一個子字串符合 $P$？

Solution

先把 $P$ 按照 * 切段成一堆小 pattern 跟 *。如果 $T$ 有一個子字串符合 $P$ 的話，那麼一定是一堆不相交的區間剛好匹配到那些不是 * 的小 pattern，且兩個相鄰區間之間有一個以上的間隔。不難看出可以從左到右 greedy，如果當前考慮的前綴恰好匹配到第一個小 pattern的話，就可以直接當成一個「$T$ 是剩下的後綴、$P$ 是剩下的小 pattern」的子問題了。要注意 * 匹配的需要是一個以上的字元，並且 $P$ 的最前最後都可以有 *。需要用 KMP 快速維護目前最前面的小 pattern 跟目前考慮的前綴是否匹配。

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef local
#define safe cerr << __LINE__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int cnt = sizeof...(T);
  (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L)
    cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

vector<int> KMP(const auto &s) {
  vector<int> fail(s.size());
  for (int i = 1, j = 0; i < (int)s.size(); i++) {
    while (j && s[i] != s[j]) j = fail[j - 1];
    if (s[i] == s[j]) ++j;
    fail[i] = j;
  }
  return fail;
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  string text, pattern;
  getline(cin, text);
  getline(cin, pattern);

  vector<string> patterns;
  {
    for (size_t i = 0, j; i < pattern.size(); i = j) {
      for (j = i; j < pattern.size(); j++)
        if ((pattern[i]=='*') != (pattern[j]=='*'))
          break;
      patterns.emplace_back(pattern.substr(i, j - i));
    }
  }

  vector<int> fail = KMP(patterns.front());
  for (size_t i = 0, j = 0; char c : text) {
    if (patterns[i] == "*") {
      ++i;
      if (i == patterns.size()) {
        cout << "Asssssss!!!!!\n";
        return 0;
      }
      fail = KMP(patterns[i]);
      continue;
    }

    while (j && c != patterns[i][j])
      j = fail[j - 1];
    if (c == patterns[i][j])
      ++j;

    if (j == patterns[i].size()) {
      j = 0;
      ++i;
      if (i == patterns.size()) {
        cout << "Asssssss!!!!!\n";
        return 0;
      }
      fail = KMP(patterns[i]);
    }
  }

  cout << "zzz...\n";
}