a308 - NOIP2011 2.统计单词数
題目描述
題目要求統計給定單詞在給定文章中出現的次數以及第一次出現的位置。匹配時不區分大小寫，但要求完全匹配，即給定的單詞必須與文章中的獨立單詞完全相同。如果給定的單詞僅是文章中某個單詞的一部分，則不算匹配。
解題思路
程式首先將給定的單詞和文章中的所有字母轉換為小寫，以便進行不區分大小寫的匹配。然後，程式遍歷文章，將文章分割成單詞。對於每個單詞，程式將其與給定的單詞進行比較。如果匹配，則增加計數器，並記錄第一次出現的位置。最後，程式輸出計數器和第一次出現的位置，如果單詞未找到，則輸出 -1。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是文章的長度，m 是給定單詞的長度。因為需要遍歷文章中的每個字符，並在每次迭代中比較單詞。
- 空間複雜度: O(m)，其中 m 是給定單詞的長度。因為需要存儲給定的單詞和當前正在比較的單詞。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a,b;
while(cin >> a){
getline(cin,b);
getline(cin,b);
int al=a.length(),bl=b.length();
for(int i=0;i<al;i++){
if(a[i]>='A'&&a[i]<='Z')
a[i]+=32;
}
for(int i=0;i<bl;i++){
if(b[i]>='A'&&b[i]<='Z')
b[i]+=32;
}
b+=' ';
string c;
int chat=-1,ans=0,n=0;
for(int i=0;i<=bl;i++){
if(b[i]==' '){
if(c==a){
if(chat==-1)
chat=n;
ans++;
}
c.clear();
n=i+1;
}
else
c+=b[i];
}
if(chat==-1)
cout << "-1\n";
else
cout << ans << " " << chat << "\n";
}
}