【GDOI 2016 Day1】第二题最长公共子串题解+代码

本文主要是介绍【GDOI 2016 Day1】第二题最长公共子串题解+代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定两个串S，T，其中串T可以在指定区间内无限制次数交换位置，求最长公共字串。

输入

前两行两个串S，T
接下来一行一个整数k表示区间个数
接下来k行每行两个整数表示一个可以修改的区间

输出

一行一个整数表示最长公共字串的长度。

样例输入

abcdafg
aafbcd
2
0 2
2 5

样例输出

题解

我先将区间都加1，这样就把区间从0..n-1变成1..n
可以发现，如果两个区间有交集，那么这两个区间可以合并。即区间[a1,b1][a2,b2]如果有交集，可以合成[a1,b2]。
对于T串中的不在任何区间内的元素i，建立一个长度为一的区间[i,i]。
这样，T就可以变成是若干个互不重合区间组成的。
开始暴力。我用的是双指针法。
求出每个区间’a’~’z’的个数，不要问我为什么。
枚举T开头位置在S的哪里，用指针维护公共子串。
设当前公共子串[i,j]合法（这段区间内S都能与T对应）
每次操作j+1，把S[j]存到一个东西里，这时就用到之前求得每个区间里每个字母的个数。如果S[j]这个字母在T对应的区间里有，且没被用光，就用一个，然后还是合法的。若对应区间里没有这个字母或在之前已经被用光了，则不合法，就把i不断+1直到合法。因为i+1就会将公共子串的前面一部分扔掉，就能给j腾出T中对应的字母。操作过程中统计答案。
时间复杂度为 $O(nm)$
可以用样例手推一下，很容易搞懂。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define N 2100
#define ord(a) a-96
using namespace std;
int f[N][N],n,m,num[N][27],now[N][27],c[N];
struct note{int x,y;
};
note a[N*100],b[N*100];
char s[N],t[N];
bool cnt(note x,note y)
{return (x.x<y.x)||(x.x==y.x && x.y<y.y);
}
int main()
{freopen("lcs.in","r",stdin);freopen("lcs.out","w",stdout);scanf("%s\n",s+1);scanf("%s\n",t+1);n=strlen(s+1);m=strlen(t+1);int tot;scanf("%d",&tot);fo(i,1,tot) scanf("%d%d",&b[i].x,&b[i].y),b[i].x++,b[i].y++;fo(i,1,m) b[++tot].x=i,b[tot].y=i;sort(b+1,b+tot+1,cnt);int tt=1,ans=0;a[1].x=b[1].x;a[1].y=b[1].y;fo(i,2,tot){if (b[i].x<=a[tt].y){a[tt].x=min(a[tt].x,b[i].x);a[tt].y=max(a[tt].y,b[i].y);}else a[++tt].x=b[i].x,a[tt].y=b[i].y;}fo(i,1,tt){fo(j,a[i].x,a[i].y){num[i][ord(t[j])]++;c[j]=i;}}int ans1,ans2,ans3;fo(l,1,m){memset(now,0,sizeof(now));int i=1,j=0,k=m-l,ki=m-l+1;while (j<l){j++;k++;int jy=ord(s[j]);now[c[k]][jy]++;while (i<l && now[c[k]][jy]>num[c[k]][jy]) now[c[ki]][ord(s[i])]--,i++,ki++;ans=max(ans,j-i+1);}ans=max(ans,j-i+1);}fo(l,1,n){memset(now,0,sizeof(now));int i=l,j=l-1,k=0,ki=1;while (j<n && k<m){j++;k++;int jy=ord(s[j]);now[c[k]][jy]++;while (i<n && ki<m && now[c[k]][jy]>num[c[k]][jy]) now[c[ki]][ord(s[i])]--,i++,ki++;ans=max(ans,j-i+1);}ans=max(ans,j-i+1);}printf("%d",ans);fclose(stdin);fclose(stdout);
}