学打字

版权声明：未经过同意不得转载 https://blog.csdn.net/qq_42500298/article/details/83107059

如果T不是S的前缀，那么S的第一个字母就一定是要打出来的。
如果T是S的前缀，那么第一步复制T是最优的。

1. 如果优方案中没有复制T答案显然不会比复制了更优。
2. 否则，找出第一次复制T的位置，并把这次复制替换为第一步，答案是不变的。
   时间复杂度为O(|S||T|)

#include<bits/stdc++.h>
using namespace std;
int n,len,ans;
char s[10005],t[1005];
int main()
{
 scanf("%s%s",s+1,t+1);
 n=strlen(s+1);
 len=strlen(t+1);
 for(int i=1;i<=n;i++)
 {
  bool flag=1;
  for(int j=1;j<=len;j++)
  {
   if(s[i+j-1]!=t[j])
   {
    flag=0;
    break;
   }
  }
  if(flag==1)
   i+=len-1;
  ans++;
 }
 printf("%d
",ans);
 return 0;
}

来源：zr