题目链接

题意简述

用$x$天时间复制字符串，有可能出错，出错就是复制上一次写过的那个字符。现在给出了原来的字符串和现在的字符串，求$x$最小是多少。

题解

显然对于一段相同而连续的字符，我们只需要关心一开始出现的那个位置。从上往下写出历史版本，用一条线连接连续相同字符一开始出现的位置，可以发现线经过的都是相同的字符。考虑线如何覆盖最优。显然线应该越低（或者说靠近原来的版本）越好。最低的位置应该是它后一个字符的线的位置$+1$。因此记个偏移量，再记个前缀和就可以解决了。

代码

#include 
    
     #include 
     
      const int maxn=1000000;int n,ans,sum[maxn+10];char s[maxn+10],t[maxn+10];int main(){
      scanf("%d%s%s",&n,s+1,t+1);  if(s[1]!=t[1])    {
          puts("-1");      return 0;    }  int f=0,k=0,now=n;  for(int i=n; i; --i)    {
          f+=sum[i+k];      if((now>i)||(t[i]!=s[now]))        {
              while((now>0)&&((now>i)||(t[i]!=s[now])))            {
                  --now;            }          if(now==i)            {
                  continue;            }          if(now<=0)            {
                  puts("-1");              return 0;            }          ++k;          ++f;          sum[i+k-1]=0;          --sum[now+k-1];        }      ans=std::max(ans,f);    }  printf("%d\n",ans);  return 0;}