6123. 哞叫時間

Week 1
2月18日

農夫約翰正在試圖向埃爾茜描述他最喜歡的 USACO 競賽，但她很難理解為什么他這么喜歡它。

他說「競賽中我最喜歡的部分是貝茜說 『現在是哞哞時間』并在整個競賽中一直哞哞叫」。

埃爾茜仍然不理解，所以農夫約翰將競賽以文本文件形式下載，并試圖解釋他的意思。

競賽被定義為一個長度為 $N$ 的小寫字母字符串。

一種哞叫一般地定義為子串 $c_i{c}_j{c}_j$，其中某字符 $c\_i$ 之后緊跟著 $2$ 個某字符 $c_j$，且 $c_i\ne c_j$。

根據農夫約翰的說法，貝茜哞叫了很多，所以如果某種哞叫在競賽中出現了至少 $F$ 次，那可能就是貝茜發出的。

然而，農夫約翰的下載可能損壞，文本文件可能存在至多一個字符與原始文件不同。

將可能的誤差考慮在內，輸出所有可能是貝茜發出的哞叫，按字母順序排序。

輸入格式

輸入的第一行包含 $N$ 和 $F$，表示字符串的長度以及貝茜的哞叫的頻次下限。

第二行包含一個長度為 $N$ 的小寫字母字符串，表示競賽。

輸出格式

輸出可能是貝茜發出的哞叫的數量，以下是按字典序排序的哞叫列表。

每行輸出一種哞叫。

數據范圍

$3\le N\le 20000$,
$1\le F\le N$

輸入樣例1：

10 2
zzmoozzmoo

輸出樣例1：

1
moo

樣例1解釋

在這個樣例中，任何字符變化都不會影響答案。

唯一貝茜可能發出的哞叫是 moo。

輸入樣例2：

17 2
momoobaaaaaqqqcqq

輸出樣例2：

3
aqq
baa
cqq

樣例2解釋

在這個樣例中，位置 $8$（從零開始索引）的 a 可能是由 b 損壞導致的，這使得 baa 成為一種貝茜發出兩次的可能的哞叫。

此外，位置 $11$ 的 q 可能是由 c 損壞導致的，這使得 cqq 成為一種貝茜可能的哞叫。

aqq 可以通過將 c 換成 a 來達到。

輸入樣例3：

3 1
ooo

輸出樣例3：

25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

---

思路：

兩種枚舉方式：

枚舉所有abb形式
時間復雜度O(26 * 25 * n)

枚舉能變化一次的字母
時間復雜度O(26*n)

code1：

n, f = map(int, input().split())
s = input()
# 生成所有可能的abb組合
abb = []
for i in range(26):for j in range(26):if i != j:str = chr(ord('a') + i) + chr(ord('a') + j) * 2abb.append(str)# 統計每個abb組合的出現次數
cnt = [0] * (26 * 25)
for i in range(len(abb)):pattern = abb[i]for j in range(n - 2):s1 = s[j:j + 3]if s1 == pattern:cnt[i] += 1# 處理出現次數為f-1的情況
for i in range(len(abb)):if cnt[i] == f - 1:pattern = abb[i]for j in range(n - 2):s1 = s[j:j + 3]# 檢查修改是否會影響原有的abb組合sign = 0for x in range(-2, 3):if 0 <= j + x <= n - 3:s2 = s[j + x:j + x + 3]if s2 == pattern:sign = 1breakif sign:continue  # 如果會影響原有的abb組合，跳過# 檢查當前子串是否可以通過修改一個字符變為abb組合if (s1[0] == pattern[0] and s1[1] == pattern[1]) or \(s1[0] == pattern[0] and s1[2] == pattern[2]) or \(s1[1] == pattern[1] and s1[2] == pattern[2]):cnt[i] += 1break  # 只能修改一次ans = []
for i in range(len(abb)):if cnt[i] >= f:ans.append(abb[i])print(len(ans))
for i in sorted(ans):print(i)

---

code2:

n, f = map(int, input().split())
# 將字符串轉換為0-25的數字表示（a-z）
s = [ord(x) - ord('a') for x in input()]# cnt[i][j] 記錄ijj出現的次數
cnt = [[0] * 26 for _ in range(26)]
ans = []def update(l, r, c):l = max(l, 0)  # 處理左邊界r = min(r, n - 1)  # 處理右邊界for i in range(l, r - 1):  # 遍歷所有可能的3字符窗口起始位置# 檢查是否是abb模式if s[i] != s[i + 1] and s[i + 1] == s[i + 2]:cnt[s[i]][s[i + 2]] += c  # 更新對應模式的計數# 如果達到閾值且是增加操作（c=1）if cnt[s[i]][s[i + 2]] >= f and c == 1:# 轉換為字符串形式ans.append(chr(ord('a') + s[i]) + chr(ord('a') + s[i + 2]) * 2)update(0, n - 1, 1)for i in range(n):  # 遍歷每個可能修改的位置temp = s[i]  # 保存原始字符# 第一步：消除當前字符對周圍的影響（c=-1）update(i - 2, i + 2, -1)  # 修改會影響前后2個位置的模式# 嘗試修改為其他字符for j in range(26):if s[i] != j:  # 跳過與原字符相同的情況s[i] = j  # 臨時修改字符# 第二步：計算修改后的影響（c=1）update(i - 2, i + 2, 1)  # 添加新字符的影響update(i - 2, i + 2, -1)  # 恢復現場s[i] = temp  # 恢復原始字符# 第三步：重新統計原始字符的影響（c=1）update(i - 2, i + 2, 1)
# 去重并排序結果
ans = sorted(set(ans))
print(len(ans))
for i in ans:print(i)

代碼邏輯解釋：

1. 預處理階段：

   • 將輸入字符串轉換為數字形式（a->0, b->1…），方便處理
   • 初始化二維計數數組cnt，用于統計每個abb模式的出現次數

2. 核心函數update：

   • 作用：在指定區間內掃描所有abb模式，并更新計數器
   • 參數c控制增加（1）或減少（-1）計數
   • 通過滑動窗口（每次檢查3個字符）的方式遍歷區間

3. 主處理流程：

   • 初始統計：調用update(0, n-1, 1)統計原始字符串中的所有abb模式
   • 遍歷每個字符位置：
     • 先消除當前字符對周圍5個字符范圍（i-2到i+2）的影響
     • 嘗試將該位置修改為其他25個字母（共26種可能）
     • 對每種可能的修改：
       • 臨時修改字符
       • 計算修改后的影響（會覆蓋前后5個字符范圍）
       • 立即回滾修改（為了不影響后續測試其他字符）
     • 最后恢復原始字符并重新統計其影響

4. 結果處理：

   • 使用set去重（可能重復添加相同模式）
   • 按字典序排序后輸出

關鍵優化點：

• 局部更新：只處理受修改影響的區域（i-2到i+2），而不是全盤重新掃描，將時間復雜度從O(n^2)降低到O(n)
• 即時回滾：在測試每個可能的字符修改時，立即回滾修改狀態，避免創建多個字符串副本

---

END
如果有更多問題或需要進一步的幫助，可以在評論區留言討論哦！
如果喜歡的話，請給博主點個關注 謝謝