Introduction to String Algorithms

A string is an ordered sequence of symbols. Competitive programming tasks might describe words, DNA, keyboard input, or sequences encoded as letters, but the central questions are often the same: where does a pattern occur, which prefixes repeat, and how can comparisons be reused instead of restarted?

This lesson establishes precise vocabulary, 0-based indexing, interval conventions, and C++17 input behavior. These details are not bookkeeping: an efficient algorithm can still be incorrect if it counts a subsequence instead of a substring, loses spaces during input, or confuses a length with a final index. The sample program is a small inspection tool, not a new matching algorithm.

Prerequisites: Arrays, loops, functions, and basic C++ string input. String positions in this folder are 0-based.

Build the idea

1. 1. Distinguish positions, lengths, and boundaries

   For s="banana", length is 6 and valid character positions are 0,1,2,3,4,5. Position 2 contains n. There are seven boundaries between or around characters, numbered 0 through 6. An empty substring can sit at any boundary even though character access s[6] does not name another stored letter.

   We use half-open intervals [L,R): include L, exclude R. The length is R−L, and adjacent pieces [0,L) and [L,N) join without overlap. In banana, [1,4) is ana, while [2,2) is empty. A valid interval satisfies 0≤L≤R≤N. C++ substr(L,R-L) takes a starting position and a length, not two endpoints.

2. 2. Name the pieces correctly

   A substring uses consecutive characters. A prefix is a substring starting at boundary 0; a suffix ends at boundary N. For banana, ban is a prefix, ana is a suffix, and nan is a substring but neither a prefix nor a suffix. A subsequence keeps order but may skip positions: bnn is a subsequence of banana, not a substring.

   A proper prefix or suffix is shorter than the entire string. A border is a proper prefix that is also a suffix: aba has border a. Prefix-function algorithms study these repeated ends. Pattern matching asks for starting positions where one whole string appears consecutively inside another; subsequence matching is a different problem with different algorithms.

3. 3. Treat input as part of the specification

   cin >> s reads one whitespace-delimited token. getline(cin,s) reads a full line and preserves spaces, including an empty line. This folder uses getline when a task accepts spaces or empty strings. Do not apply cin >> ws before getline if leading spaces or blank strings are meaningful; it would remove them. If earlier formatted input left a newline, consume that exact remaining newline deliberately.

   The examples use ordinary byte strings, as most contests do for ASCII alphabets. std::string::size() counts stored char elements, not Unicode characters a reader perceives. A UTF-8 letter may occupy several bytes. Unless a problem explicitly provides a Unicode model, the implementations compare bytes exactly and distinguish uppercase from lowercase. They do not normalize accents or ignore spaces.

4. 4. Predict the cost of common operations

   Reading N characters, scanning them, copying a length-N string, or printing them requires linear work. Accessing a known index is constant time. Comparing two strings may inspect characters up to their first difference, so its worst-case cost is linear in the shorter length. Creating a substring usually copies its selected characters; repeatedly making long substrings inside nested loops can be expensive.

   Appending one character to a std::string is amortized constant time under its usual dynamic-storage behavior, but building a growing string by repeatedly assigning s = s + c may repeatedly copy the old content. Later linear-time matching algorithms compare characters by index and reuse previously computed information instead of manufacturing a new substring at every start position.

5. 5. Inspect an example before optimizing it

   The program reads banana bandana and interval [2,6). It prints length 14, substring nana, the length-2 prefix ba, the length-2 suffix na, and the count 6 of lowercase a. It first checks endpoints, so an invalid range cannot accidentally become a huge unsigned length.

   It stores N as int under the stated length limit of one million, while using explicit conversions at the string boundary. For an empty input line, the only valid interval is [0,0): all three selected pieces are empty and the count is zero. In matching lessons we explicitly adopt another convention: the empty pattern matches all N+1 boundaries. Keeping these choices visible makes edge cases predictable instead of accidental.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s); // Preserve spaces and allow an empty input string.
    int left,right;
    cin>>left>>right;
    int n=static_cast<int>(s.size()); // Contract: length <= 1,000,000.
    // Half-open intervals may end at n, but must not go outside the string.
    if(left<0||right<left||right>n){
        cout<<"INVALID\n";
        return 0;
    }
    int countA=0;
    for(char c:s){
        if(c=='a'){
            ++countA; // Count exact lowercase bytes.
        }
    }
    cout<<n<<'\n';
    cout<<s.substr(left,right-left)<<'\n'; // substr takes a length.
    cout<<s.substr(0,left)<<'\n'; // Prefix of length left.
    cout<<s.substr(n-left,left)<<'\n'; // Suffix of the same length.
    cout<<countA<<'\n';
}

Complexity analysis

O(N) time including input, the frequency scan, and copying/printing the selected pieces. The stored string and temporary substrings use O(N) space. A single indexed character access is O(1); constructing a length-K substring is O(K).

Example input and output

Line 1: string s, possibly empty and including spaces, with length at most 1,000,000. Then integers L R. Output length, s[L..R), prefix of length L, suffix of length L, and the number of lowercase a characters, each on its own line. Invalid endpoints produce INVALID.

Input

banana bandana
2 6

Output

14
nana
ba
na
6

The interval includes positions 2,3,4,5. Prefix and suffix lengths are both L=2. The two words contain three lowercase a characters each.

Practical applications

Establish an input model for matching, prefix arrays, Z-arrays, tries, hashing, and suffix structures. Before choosing an algorithm, state the alphabet, indexing, whether matches may overlap, and how empty strings are interpreted.

Check your understanding

For a half-open substring [L,R), what is its length?

Put it into practice

Extend the inspection program to print whether the selected substring is also a prefix of the whole input string.