C++ Text Processing Software – Problem P5734 from Luogu

Click the blue text

Follow us

P5734 Text Processing Software

Problem Description

You need to develop a text processing software. Initially, input a string as the starting document. You can consider the beginning of the document as the first character. The following operations need to be supported:

• 1 str: Append the string to the end of the document and output the document’s string;

• 2 a b: Substring the document, keeping only the characters from the a-th character for b characters, and output the document’s string;

• 3 a str: Insert the string str before the a-th character in the document, and output the document’s string;

• 4 str: Find the substring, searching for the string str in the document and output the first position; if not found, output -1.

To simplify the problem, it is stipulated that the initial document and each operation’s str do not contain spaces or newlines. There will be at most q operations.

Input Format

• The first line inputs a positive integer q , indicating the number of operations.

• The second line inputs a string doc , indicating the initial string.

• From the third line onwards, each line represents an operation as described in the problem.

Output Format

• A total of q lines will be output.

• For each operation, output a string according to the operation’s requirements.

• For operation 4, output an integer according to the operation’s requirements.

Input Example

#1

4

ILove

1 Luogu

2 5 5

3 3 guGugu

4 gu

Output Example

#1

ILoveLuogu

Luogu

LuoguGugugu

3

Explanation/Hint

The data guarantees that the initial string length is n .

💡 Problem Analysis

This problem simulates a simple text processor, implementing four types of operations: append, substring, insert, and find. The input does not contain spaces, and all strings can be read using >>, processed in order, and output results immediately after each operation.

💡 Solution Approach

1. Maintain the current document using a string variable doc.

2. Read the operation number op and branch:

1. op=1: doc += str.

2. op=2: doc = doc.substr(a, b), note that this replaces with the substring result.

3. op=3: doc.insert(a, str).

4. op=4: doc.find(str), if it returns string::npos output -1, otherwise output the position.

3. The problem guarantees valid parameters, so no additional boundary checks are needed. The overall implementation is straightforward and clear.

📐Mathematical Principles

• String positions are counted from 0.

• substr(a, b) means: take a segment starting from index a with length b (if a+b exceeds bounds, it does not occur in this problem).

• The find function returns the starting index of the first match; if no match is found, it returns a special value npos (usually a large unsigned equivalent of -1).

🧰 Programming Principles

• C++’s std::string encapsulates a dynamic array-like character sequence, supporting append (expansion), insertion (moving the latter part), and substring (constructing a new string).

• Each modification will involve internal memory movement or object creation (which has a linear impact on time complexity, see complexity details).

🧾Code Implementation

#include<iostream>   // Standard input output#include<string>     // String type and related member functionsusing namespace std;
int main(){    ios::sync_with_stdio(false); // Improve IO efficiency    cin.tie(nullptr);            // Unbind cin and cout
    int q;            // Number of operations    string doc;       // Current document content    cin >> q;         // Read operation count    cin >> doc;       // Read initial string
    // Process q operations one by one    for (int i = 0; i < q; ++i) {        int op;       // Operation number (1/2/3/4)        cin >> op;    // Read operation number
        if (op == 1) {            // 1 str: Append the string str to the end of the document and output the document            string str;            cin >> str;           // Read the substring to append (no spaces)            doc += str;           // Equivalent to doc.append(str), appending str to the end of the document            cout << doc << "\n";  // Output current document        } elseif (op == 2) {            // 2 a b: Substring the document, keeping only from the a-th character for b characters and outputting the document            int a, b;            cin >> a >> b;        // Read starting point a and length b            // string::substr(pos, count) returns a substring starting from pos with length count            // The problem guarantees valid parameters, so we can directly assign            doc = doc.substr(a, b);            cout << doc << "\n";  // Output current document        } elseif (op == 3) {            // 3 a str: Insert str before the a-th character in the document and output the document            int a;            string str;            cin >> a >> str;      // Read position a and the substring to insert            // string::insert(pos, s) inserts s before position pos            doc.insert(a, str);            cout << doc << "\n";  // Output current document        } elseif (op == 4) {            // 4 str: Find the substring and output the first occurrence position; if not found, output -1            string str;            cin >> str;           // Read the substring to find            size_t pos = doc.find(str); // string::find returns the first occurrence position or string::npos            if (pos == string::npos) {                cout << -1 << "\n";     // Not found            } else {                cout << static_cast<int>(pos) << "\n"; // Output found position (starting from 0)            }        }    }    return 0; // Program ends}

Click below to read the original text

Direct access to Luogu problem bank for practice

🧭 Code Analysis

• ios::sync_with_stdio(false); cin.tie(nullptr);: Speed up IO.

• doc += str;: Equivalent to doc.append(str), appending str to the end.

• doc = doc.substr(a, b);: Directly overwrite the original document with the substring result.

• doc.insert(a, str);: Insert before position a.

• The return type of find is size_t, output it using static_cast<int> to convert to the integer index as per the problem’s convention.

🛠️ Programming Tips

• Using member functions to manipulate strings is more robust and concise than writing loops manually.

• For failed searches, use pos == string::npos to check, do not compare directly with -1 (different types).

• For frequent outputs, remember to use \n instead of endl to avoid extra flushes affecting performance.

• If the input volume is large, enabling fast IO in advance can significantly reduce time (this problem is not large, but the method can be reused).

📚 Function / Method Usage Instructions

• string::append(const string&) / operator+=: Append to the end.

• string::substr(size_t pos, size_t count): Substring.

• string::insert(size_t pos, const string& s): Insert s before pos.

• string::find(const string& s): Returns the first occurrence position or npos.

• string::size() / length(): Current length.

• cin >> x: Read separated by whitespace; since this problem’s strings do not contain spaces, they can be read directly.

🔤 Variables and Functions “Word Card”

• string: String

• append / +=: Append

• substr: Substring

• insert: Insert

• find: Find

• npos: Not found flag value

• size/length: Length

• position / index: Position/index

• document(doc): Document (variable name)

• operation(op): Operation (variable name)

⏱️ Time & Space Complexity Analysis

• Let the current document length be n, and the operation string length be m:

• op=1 append: O(m) (may trigger expansion and copying).

• op=2 substring: O(b) (constructing a new string of length b).

• op=3 insert: O(n + m) (moving the latter part + inserting).

• op=4 find: Worst O(n * m), but library implementations usually optimize (e.g., double ring or Boyer-Moore variants).

• Overall, under the problem scale (q ≤ 100, initial |s| ≤ 100), it runs comfortably.

🧩 Problem Summary

This problem tests the proficiency of basic string operations and the correct use of library functions. Focus on the four keywords: append, substring, insert, find, corresponding to += / append, substr, insert, find, to complete all functionalities with extremely simple and clear code. Good IO habits and attention to the details of npos checking are points that enhance the standard implementation.

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 effective learning methods and educational concepts

• Discover 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