統(tǒng)計(jì)單詞數(shù)

題目描述

一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)。

現(xiàn)在，請你編程實(shí)現(xiàn)這一功能，具體要求是：給定一個(gè)單詞，請你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時(shí)，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨(dú)立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例 1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例 2）。

輸入格式

共 2行。

第 1 行為一個(gè)字符串，其中只含字母，表示給定單詞；

第 2 行為一個(gè)字符串，其中只可能包含字母和空格，表示給定的文章。

輸出格式

一行，如果在文章中找到給定單詞則輸出兩個(gè)整數(shù)，兩個(gè)整數(shù)之間用一個(gè)空格隔開，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時(shí)，單詞首字母在文章中的位置，位置從 0 開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一個(gè)整數(shù) ?1。

注意：空格占一個(gè)字母位

輸入輸出樣例

輸入 #1

To
to be or not to be is a question

輸出 #1

2 0

輸入 #2

to
Did the Ottoman Empire lose its power at that time

輸出 #2

-1

說明/提示

數(shù)據(jù)范圍

1≤ 第一行單詞長度 ≤10。

1≤ 文章長度 ≤10^6。

解

這道題我先說一下錯誤思路，算是提供一下反例吧，

最開始我的思路是利用C++的流式字符串的特性把各個(gè)單詞分開然后存儲到一個(gè)字符串?dāng)?shù)組中，然后匹配字符串?dāng)?shù)組中數(shù)組元素，小寫匹配看是否與目標(biāo)單詞一致，若一致，則計(jì)數(shù)器加一，記錄首次符合條件的數(shù)組元素下標(biāo)，然后根據(jù)下標(biāo)計(jì)算前面有多少個(gè)字符，也就是在原字符串的首次出現(xiàn)下標(biāo)。

這里面其實(shí)有個(gè)關(guān)鍵問題，就是我們并不能確定每個(gè)單詞之間相隔多少個(gè)空格

這就導(dǎo)致了我們在流式操作后，無法計(jì)算得到正確的首次出現(xiàn)的下標(biāo)位置

---

沒辦法，這種操作是行不通的，那么只能傳統(tǒng)的使用滑動窗口的方式了，

設(shè)置滑動窗口大小為目標(biāo)單詞長度，再均變?yōu)樾懽帜负蟊闅v字符串的對應(yīng)窗口，看窗口內(nèi)字符是否與目標(biāo)單詞匹配。這里面要注意循環(huán)時(shí)的結(jié)束條件，應(yīng)為字符串長度-滑動窗口長度+1

當(dāng)然，還有之后還有一步判斷，就是保證成功匹配的是一個(gè)獨(dú)立的單詞而不是某單詞的前綴，

這要求若滑動窗口不在首尾，前后一定是空格

若上述條件均滿足，計(jì)數(shù)器加一，記錄首次出現(xiàn)的位置即可

#include<bits/stdc++.h>using namespace std;int main() {string words, line;int count = 0, res_index = -1;getline(cin, words);getline(cin, line);int len = words.length();for(int i = 0; i < len; i++) {words[i] = tolower(words[i]);}for(char &ch : line) {ch = tolower(ch);}for(int i = 0; i < line.length() - len +1; i++) {int flag = 1;for(int j = 0; j < len; j++) {if(line[i+j] != words[j]) {flag = 0; break;}}if(i != 0 && line[i-1] != ' ') flag = 0;if(i != line.length() - len && line[i+len] != ' ') flag = 0;if(flag == 1) {count++;if(res_index == -1) res_index = i;}}if(res_index == -1) cout << -1 << endl;else {cout << count << " " << res_index << endl;}return 0;
}