f341 - 5.閱讀順序(Reading)
題目描述
題目要求給定一個字串 S 和一個翻轉軸字串 T，將 S 根據 T 進行翻轉，翻轉規則為 T 不動，T 左右兩側的字串交換位置並各自顛倒順序。
解題思路
程式首先讀取翻轉前的字串 S 和翻轉軸字串 T。然後，它尋找 T 在 S 中第一次出現的位置。找到 T 的位置後，程式將 T 左右兩側的字串交換位置，並各自顛倒順序。最後，程式輸出翻轉後的字串。核心邏輯是找到翻轉軸，然後將字串分割成三部分：翻轉軸左側、翻轉軸本身、翻轉軸右側。然後交換左右兩側，並分別反轉。
複雜度分析
- 時間複雜度: O(nm)，其中 n 是 S 的長度，m 是 T 的長度。尋找 T 在 S 中第一次出現需要 O(nm) 的時間。交換和反轉字串需要 O(n) 的時間。
- 空間複雜度: O(n)，用於儲存字串 S、T 和翻轉後的字串。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
char a[51],f[51],al,fl,fd=-1;
int main(){
while(a[al]=getchar_unlocked()){
if(a[al]<'a')break;++al;
}
while(f[fl]=getchar_unlocked()){
if(f[fl]<'a')break;++fl;
}
for(char i=0;i<al&&fd==-1;++i){
if(a[i]==f[0]){
char c=0;
for(char j=i,cn=0;cn<fl;++cn,++j){
if(a[j]!=f[cn]){
c=1;
break;
}
}
if(!c){
fd=i;
break;
}
}
}
fd+=fl-1;
for(char i=al-1;i>=0;--i){
if(i==fd){
i-=fl;
char j=0;
while(j<fl){
putchar_unlocked(f[j]);
++j;
}
}
putchar_unlocked(a[i]);
}
}