通过添加字符或追加字符串本身来形成字符串的最小移动

给定一个字符串S，我们需要编写一个程序来检查是否可以通过多次执行以下任何操作来构造给定的字符串S。在每一步中，我们都可以：

• 在字符串末尾添加任意字符。
• 或者，将字符串附加到字符串本身。

上述步骤可以应用任意次数。我们需要编写一个程序来打印形成字符串所需的最小步骤。

例如：

Input : aaaaaaaa
Output : 4 
Explanation: move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: append "aa" to form "aaaa" 
move 4: append "aaaa" to form "aaaaaaaa" 

Input: aaaaaa
Output: 4 
Explanation: move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: add 'a' to form "aaa" 
move 4: append "aaa" to form "aaaaaa" 

Input: abcabca
Output: 5  

解决这个问题的方法是使用 动态规划 计算最小移动次数。创建一个名为 数据处理 大小为n，其中n是输入字符串的长度。dp[i]存储生成子串（0…i）所需的最小移动次数。根据问题，有两种可能的举措：

1. dp[i]=min（dp[i]，dp[i-1]+1） 这意味着增加了字符。
2. dp[i*2+1]=min（dp[i]+1，dp[i*2+1]） ，如果s[0…i]==s[i+1..i*2+1]，则完成字符串的追加

   答案将存储在 dp[n-1] 因为我们需要形成字符串（0..n-1）索引。

   以下是上述理念的实施：

   C++

   // CPP program to print the // Minimal moves to form a string // by appending string and adding characters #include <bits/stdc++.h> using namespace std; // function to return the minimal number of moves int minimalSteps(string s, int n) { int dp[n]; // initializing dp[i] to INT_MAX for ( int i = 0; i < n; i++) dp[i] = INT_MAX; // initialize both strings to null string s1 = "" , s2 = "" ; // base case dp[0] = 1; s1 += s[0]; for ( int i = 1; i < n; i++) { s1 += s[i]; // check if it can be appended s2 = s.substr(i + 1, i + 1); // addition of character takes one step dp[i] = min(dp[i], dp[i - 1] + 1); // appending takes 1 step, and we directly // reach index i*2+1 after appending // so the number of steps is stord in i*2+1 if (s1 == s2) dp[i * 2 + 1] = min(dp[i] + 1, dp[i * 2 + 1]); } return dp[n - 1]; } // Driver Code int main() { string s = "aaaaaaaa" ; int n = s.length(); // function call to return minimal number of moves cout << minimalSteps(s, n); return 0; }

   JAVA

   // Java program to print the // Minimal moves to form a string // by appending string and adding characters import java.util.*; class GFG { // function to return the minimal number of moves static int minimalSteps(String s, int n) { int []dp = new int [n]; // initializing dp[i] to INT_MAX for ( int i = 0 ; i < n; i++) dp[i] = Integer.MAX_VALUE; // initialize both strings to null String s1 = "" , s2 = "" ; // base case dp[ 0 ] = 1 ; s1 += s.charAt( 0 ); for ( int i = 1 ; i < n; i++) { s1 += s.charAt(i); // check if it can be appended s2 = s.substring(i + 1 , i + 1 ); // addition of character takes one step dp[i] = Math.min(dp[i], dp[i - 1 ] + 1 ); // appending takes 1 step, and we directly // reach index i*2+1 after appending // so the number of steps is stord in i*2+1 if (s1 == s2) dp[i * 2 + 1 ] = Math.min(dp[i] + 1 , dp[i * 2 + 1 ]); } return dp[n - 1 ]; } // Driver Code public static void main(String args[]) { String s = "aaaaaaaa" ; int n = s.length(); // function call to return minimal number of moves System.out.println(minimalSteps(s, n)/ 2 ); } } // This code is contributed by // Shashank_Sharma

   Python3

   # Python program to print the # Minimal moves to form a string # by appending string and adding characters INT_MAX = 100000000 # function to return the # minimal number of moves def minimalSteps(s, n): dp = [INT_MAX for i in range (n)] # initialize both strings to null s1 = "" s2 = "" # base case dp[ 0 ] = 1 s1 + = s[ 0 ] for i in range ( 1 , n): s1 + = s[i] # check if it can be appended s2 = s[i + 1 : i + 1 + i + 1 ] # addition of character # takes one step dp[i] = min (dp[i], dp[i - 1 ] + 1 ) # appending takes 1 step, and # we directly reach index i*2+1 # after appending so the number # of steps is stord in i*2+1 if (s1 = = s2): dp[i * 2 + 1 ] = min (dp[i] + 1 , dp[i * 2 + 1 ]) return dp[n - 1 ] # Driver Code s = "aaaaaaaa" n = len (s) # function call to return # minimal number of moves print ( minimalSteps(s, n) ) # This code is contributed # by sahilshelangia

   C#

   // C# program to print the // Minimal moves to form a string // by appending string and adding characters using System; class GFG { // function to return the minimal number of moves static int minimalSteps(String s, int n) { int []dp = new int [n]; // initializing dp[i] to INT_MAX for ( int i = 0; i < n; i++) dp[i] = int .MaxValue; // initialize both strings to null String s1 = "" , s2 = "" ; // base case dp[0] = 1; s1 += s[0]; for ( int i = 1; i < n; i++) { s1 += s[i]; // check if it can be appended s2 = s.Substring(i , 1); // addition of character takes one step dp[i] = Math.Min(dp[i], dp[i - 1] + 1); // appending takes 1 step, and we directly // reach index i*2+1 after appending // so the number of steps is stord in i*2+1 if (s1 == s2) dp[i * 2 + 1] = Math.Min(dp[i] + 1, dp[i * 2 + 1]); } return dp[n - 1]; } // Driver Code public static void Main(String []args) { String s = "aaaaaaaa" ; int n = s.Length; // function call to return minimal number of moves Console.Write(minimalSteps(s, n)/2); } } // This code has been contributed by 29AjayKumar

   PHP

   <?php // php program to print the // Minimal moves to form a // string by appending string // and adding characters // function to return the // minimal number of moves function minimalSteps( $s , $n ) { // initializing dp[i] to INT_MAX for ( $i = 0; $i < $n ; $i ++) $dp [ $i ] = PHP_INT_MAX; // initialize both // strings to null $s1 = "" ; $s2 = "" ; // base case $dp [0] = 1; $s1 = $s1 . $s [0]; for ( $i = 1; $i < $n ; $i ++) { $s1 = $s1 . $s [ $i ]; // check if it can // be appended $s2 = substr ( $s , $i + 1, $i + 1); // addition of character // takes one step $dp [ $i ] = min( $dp [ $i ], $dp [ $i - 1] + 1); // appending takes 1 step, // and we directly // reach index i*2+1 // after appending // so the number of steps // is stord in i*2+1 if ( $s1 == $s2 ) $dp [ $i * 2 + 1] = min( $dp [ $i ] + 1, $dp [ $i * 2 + 1]); } return $dp [ $n - 1]; } // Driver Code $s = "aaaaaaaa" ; $n = strlen ( $s ); // function call to return //minimal number of moves echo minimalSteps( $s , $n ); // This code is contributed by mits ?>

   输出：

   4
   

   时间复杂性： O（n） ^2. )，其中n是输入字符串的长度。