C++ Word Count Program [NOIP 2011 Popular Group] P1308

Click the blue text

Follow us

P1308 [NOIP 2011 Popular Group] Word Count

Problem Description

Most text editors have a feature to find words, which can quickly locate specific words in a document, and some can also count the occurrences of a specific word in the text.

Now, please implement this functionality in your program. The specific requirements are: given a word, output the number of times it appears in the given article and the position of its first occurrence. Note: when matching words, case sensitivity is ignored, but a complete match is required, meaning the given word must exactly match an independent word in the article (see Sample 1). If the given word is only part of a word in the article, it does not count as a match (see Sample 2).

Input Format

• There are lines.

• The first line is a string containing only letters, representing the given word;

• The second line is a string that may only contain letters and spaces, representing the given article.

Output Format

• One line. If the given word is found in the article, output two integers separated by a space, which are the number of occurrences of the word in the article and the position of its first occurrence (i.e., the position of the first letter of the word in the article, starting from 0); if the word does not appear in the article, output an integer -1.

• Note: spaces count as one character.

Input Sample

#1

To

to be or not to be is a question

#2

to

Did the Ottoman Empire lose its power at that time

Output Sample

#1

2 0

#2

-1

Explanation/Hint

Data range

The length of the first line word .

The length of the article .

NOIP 2011 Popular Group Problem 2

💡 Problem Analysis

The problem requires us to find a target word in a given article and return its occurrence count and the position of its first occurrence. The matching should ignore case, and the starting position of the word must be accurately reported. It is important to note that words are separated by spaces, and there may be multiple words in the article that match the target word.

💡 Solution Approach

To implement this functionality, we can follow these steps:

1. Input Handling: Read the target word and article content.

2. Word Matching: Check each word in the article content one by one, ignoring case, to find the target word.

3. Position Calculation: Record the position of the first occurrence of the target word and count its occurrences.

4. Output Result: Depending on whether the target word exists, output its occurrence count and the character position of its first occurrence; if the target word is not found, output -1.

📐Mathematical Principles

• String Matching Algorithm: We can find the target word in the article by comparing characters one by one. This is a common string search technique, especially suitable for short target words and case-insensitive matching.

• Position Calculation: By traversing the string and constructing words, we can record the starting position of the target word when it is matched.

🧰 Programming Principles

• String Operations: Use the string type for string storage and processing. Utilize isalpha() to check for letters and tolower() for case conversion.

• Traverse the Article: By traversing the article character by character and separating words based on spaces or non-letter characters.

• Matching and Recording Position: Each time the target word is found, update the occurrence count and record the character position of its first occurrence.

Code Implementation

#include<iostream>#include<string>#include<algorithm>using namespace std;
int main(){    // Read input    string targetWord, article;    getline(cin, targetWord);  // Read target word    getline(cin, article);     // Read article content
    // Convert target word to lowercase to ensure case-insensitive matching    transform(targetWord.begin(), targetWord.end(), targetWord.begin(), ::tolower);
    // Initialize variables    int count = 0;  // To record the occurrence count of the target word    int firstPosition = -1;  // Record the first occurrence position of the target word        // Traverse the article for word matching    size_t position = 0;  // Current character position    size_t firstPos = string::npos;  // Record the first occurrence position of the target word
    for (size_t i = 0; i < article.length(); i++) {        // If it is a letter, start constructing a word        if (isalpha(article[i])) {            size_t start = i;  // Starting position of the current word            string word = "";  // Store the current word                        // Continue constructing the current word until a non-letter character is encountered            while (i < article.length() && isalpha(article[i])) {                word += tolower(article[i]);  // Convert to lowercase                i++;            }                        // Check if the current word matches the target word            if (word == targetWord) {                count++;  // Match successful, increase count                if (firstPos == string::npos) {                    firstPos = start;  // Record the starting position of the first occurrence                }            }        }    }
    // Output result    if (count > 0) {        cout << count << " " << firstPos << endl;  // Output count and first occurrence position    } else {        cout << -1 << endl;  // Target word not found    }
    return 0;}

Click below to read the original text

Direct access to the Luogu question bank for practice

🛠️ Programming Tips

• Using transform for case conversion: The transform function allows us to easily convert all characters in a string to lowercase, which is very effective for case-insensitive matching.

• String Splitting and Character Comparison: By traversing the article character by character and using isalpha() to identify letters, we can construct words and avoid interference from spaces or punctuation.

• Using string::npos to mark the first position: string::npos is a special value used to indicate that the target word has not yet been found. When the first match occurs, we can record its position.

📚 Function / Method Usage Instructions

• getline(cin, targetWord):

• Function: Reads a line of string from standard input.

• Usage: getline allows us to read a complete line containing spaces until a newline character is encountered.

• transform(begin, end, output, func):

• Function: Applies the specified function (such as tolower()) to each character of the string.

• Usage: This function can be used to uniformly convert characters in a string.

• isalpha(c):

• Function: Checks if a character is a letter (case insensitive).

• Usage: When traversing the article, use isalpha to determine if the current character is a letter; non-letter characters end the construction of the current word.

• tolower(c):

• Function: Converts a character to lowercase.

• Usage: Used to ensure that string comparisons are case insensitive.

• string::npos:

• Function: A special constant indicating an invalid position.

• Usage: When the target word first appears, record its position and compare it with npos to determine if the target word has been found.

🔤 Variables and Functions “Word Card”

• targetWord:

• Type: string

• Meaning: Stores the target word for matching against words in the article.

• Usage: Matches against words in the article by converting case.

• article:

• Type: string

• Meaning: Stores the content of the article.

• Usage: Extracts words from it and compares them with the target word.

• count:

• Type: int

• Meaning: Records the number of occurrences of the target word in the article.

• Usage: Increments by 1 each time a matching word is found.

• firstPosition:

• Type: int

• Meaning: Records the character position of the first occurrence of the target word.

• Usage: Saves the starting position of the word when the first match is found.

• firstPos:

• Type: size_t

• Meaning: An auxiliary variable used to save the starting position of the target word’s first occurrence.

• Usage: Determines if the target word has been found by comparing with string::npos.

• position:

• Type: size_t

• Meaning: The current character position being processed.

• Usage: Used to track the character position while traversing the article.

⏱️ Time & Space Complexity Analysis

• Time Complexity: O(n)

• Where n is the length of the article. We traverse the entire article once, and each operation is constant time. Therefore, the time complexity is linear.

• Space Complexity: O(1)

• We use a small amount of extra space to store the target word and intermediate variables, so the space complexity is constant.

🧩 Problem Summary

This problem tests techniques such as character-by-character traversal of strings, word matching, case insensitivity, and position calculation. In the implementation process, we efficiently calculate the occurrence count and position of the target word by traversing the article character by character and constructing words, avoiding interference from spaces and punctuation. This method has good time and space efficiency and can adapt to the processing needs of large-scale data.

END

Like

Collect

Share

Explore the forefront of educational technology and empower future learning!

“Bit Island Education Technology” is committed to using innovative technology to create a more efficient, interesting, and future-oriented learning experience.

• Get the latest educational technology products and course materials

• Learn practical and efficient learning methods and educational concepts

• Understand innovative teaching tools and classroom application cases

• Participate in exclusive events and win learning benefits

Scan the code to follow us and start your journey in smart education! 👇

BIT ISLAND

Long press to scan

WeChat ID丨bit_island_Terry

WeChat Search丨Bit Island Education Technology