Text Editor

Michael is working on a very basic text editor. Initially, nothing is written on the editor. Also, the editor stores a buffer which is initially empty. In one operation, Michael can do one of the following operations-

1. Append any lowercase English character to the current string on the editor. After this operation, the buffer becomes empty (if anything was stored in the buffer previously).

2. Copy the current string on the editor to the buffer. Note that the complete string gets copied. You can't copy strings partially. Any previously stored string in the buffer is replaced.

3. Append the string in the buffer to the current string. Note that after this operation, the buffer is still intact.

You are given a string A. Help Michael find the minimum number of operations required to write the string A on the editor.

1 <= |A| <= 5 x 10⁵

Input 1:

  A : "abababababab"

  A : "aaaabaaaab"

Output 1:

  7

  7

Explanation 1:

  One of the ways to write this string in 7 operations is-
  1. Append 'a' to the editor. Current string = "a", Current Buffer = "" 
  2. Append 'b' to the editor. Current string = "ab", Current Buffer = ""
  3. Copy the string to buffer. Current string = "ab", Current Buffer = "ab"
  4. Append the string in buffer to current string. Current string = "abab", Current Buffer = "ab"
  5. Append the string in buffer to current string. Current string = "ababab", Current Buffer = "ab"
  6. Copy the string to buffer. Current string = "ababab", Current Buffer = "ababab"
  7. Append the string in buffer to current string. Current string = "abababababab", Current Buffer = "ababab"

  One of the ways to write this string in 7 operations is-
  1. Append 'a' to the editor. Current string = "a", Current Buffer = "" 
  2. Append 'a' to the editor. Current string = "aa", Current Buffer = "" 
  3. Copy the string to buffer. Current string = "aa", Current Buffer = "aa"
  4. Append the string in buffer to current string. Current string = "aaaa", Current Buffer = "aa"
  5. Append 'b' to the editor. Current string = "aaaab", Current Buffer = "" 
  6. Copy the string to buffer. Current string = "aaaab", Current Buffer = "aaaab"
  7. Append the string in buffer to current string. Current string = "aaaabaaaab", Current Buffer = "aaaab"