TOJ 18

題目

https://toj.tfcis.org/oj/pro/18/

輸入一個字串 $S$

定義一個字串是強效字串，唯有在 $S$ 只留下英文字母時，從頭看到尾與從尾看到頭，不分大小寫是相同的

如果是強效字串，在字串前加上 SETUP!

想法

先利用一個 tmp 字串記錄字串 $S$ 去除英文字母以外的字元，且將字母都轉為小寫的樣子

接下來只需要檢查 tmp 是不是回文即可

判斷方式可以從同到字串的頭到字串的一半，檢查頭尾是否相同

也就是 $tmp[i] = tmp[tmp.size()-1-i]$ 是否成立

Code

//By Koios1143
#include<iostream>
using namespace std;
int main(){
	string s;
	while(getline(cin,s)){
		string tmp="";
		for(int i=0 ; i<s.size() ; i++){
			if((s[i]>='A' && s[i]<='Z') || (s[i]>='a' && s[i]<='z'))
				tmp+=tolower(s[i]);
		}
		bool powerful=true;
		for(int i=0, j=tmp.size()-1 ; i<tmp.size()/2 ; i++, j--){
			if(tmp[i]!=tmp[j]){
				powerful=false;
				break;
			}
		}
		if(powerful)
			cout<<"SETUP! "<<s<<"\n";
		else
			cout<<s<<"\n";
	}
	return 0;
}

複雜度分析

總複雜度約為 $O(2len(s))$