题意：
求A,B串连续子串首尾相连形成的项链中，最长的相同的项链长度及子串的初始位置。
项链旋转，翻转后相同就被视为相同。
分析:
首先，两条项链相同，那么它们在原串中有这样的形状：
只考虑旋转后相同的字符串，我们可以将其分成两段，分别处理。
对于每个位置对 （ i , p ） （i,p） （i,p）,我们希望求出从 i i i向左延伸到最远的 q q q,从 p p p向右延伸到最远的 j j j,使得 A [ q , i ] = B [ p , j ] A[q,i]=B[p,j] A[q,i]=B[p,j],将 L L L记为 g [ i ] [ p ] g[i][p] g[i][p]。
同理，我们还要求出从 i + 1 i+1 i+1向右延伸到最远的 x x x,从 p − 1 p-1 p−1向左延伸到最远的 y y y,使得 A [ i + 1 , x ] = B [ y , p − 1 ] A[i+1,x]=B[y,p-1] A[i+1,x]=B[y,p−1],将它的长度记为 f [ i + 1 ] [ p − 1 ] f[i+1][p-1] f[i+1][p−1]。
这样我们就得到了在 （ i , p ） （i,p） （i,p）分成两段的相同项链的最大长度。
现在的问题变成怎么求 g [ i ] [ p ] g[i][p] g[i][p]和 f [ i + 1 ] [ p − 1 ] f[i+1][p-1] f[i+1][p−1]。
定义一个辅助的数组 d p [ i ] [ j ] dp[i][j] dp[i][j]表示从 i i i向左延伸到最远的 q q q，从 j j j向左延伸到最远的 p p p，使得 A [ q , i ] = B [ p , j ] A[q,i]=B[p,j] A[q,i]=B[p,j],将 L L L记为 d p [ i ] [ j ] dp[i][j] dp[i][j]
如果 A [ i ] = = A [ j ] A[i]==A[j] A[i]==A[j],则 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j]=dp[i-1][j-1]+1 dp[i][j]=dp[i−1][j−1]+1;
否则 d p [ i ] [ j ] = 0 dp[i][j]=0 dp[i][j]=0。
求出 d p [ i ] [ j ] dp[i][j] dp[i][j]后，用 d p dp dp数组算出相应的左端点，更新 g g g数组和 f f f数组。
最后：
g [ i ] [ j ] = m a x ( g [ i ] [ j ] , g [ i ] [ j − 1 ] − 1 ) g[i][j]=max(g[i][j],g[i][j-1]-1) g[i][j]=max(g[i][j],g[i][j−1]−1)
f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ] [ j + 1 ] − 1 ) f[i][j]=max(f[i][j],f[i][j+1]-1) f[i][j]=max(f[i][j],f[i][j+1]−1)
考虑翻转，将B串翻转过来再做一遍相同的操作即可。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 3005
int dp[MAXN][MAXN],g[MAXN][MAXN],f[MAXN][MAXN],ns,nt,ps,pt,ans;
char s[MAXN],t[MAXN];
void Work(bool flag)
{
for(int i=max(ns,nt);i>=0;i--) dp[0][i]=dp[i][0]=0;
for(int i=0;i<=ns;i++)
for(int j=0;j<=nt;j++) g[i][j]=f[i][j]=0;
for(int i=1;i<=ns;i++)
for(int j=1;j<=nt;j++)
if(s[i]==t[j])
{
dp[i][j]=dp[i-1][j-1]+1;
g[i][j-dp[i][j]+1]=max(g[i][j-dp[i][j]+1],dp[i][j]);
f[i-dp[i][j]+1][j]=max(f[i-dp[i][j]+1][j],dp[i][j]);
}
else dp[i][j]=0;
for(int i=1;i<=ns;i++)
for(int j=1;j<=nt;j++)
g[i][j]=max(g[i][j],g[i][j-1]-1);
for(int i=1;i<=ns;i++)
for(int j=nt;j>=1;j--)
f[i][j]=max(f[i][j],f[i][j+1]-1);
for(int i=0;i<=ns;i++)
for(int j=0;j<=nt;j++)
if(g[i][j+1]+f[i+1][j]>ans)
{
ans=g[i][j+1]+f[i+1][j];
ps=i-g[i][j+1];
pt=j-f[i+1][j];
if(flag) pt=nt-pt-ans;
}
}
int main()
{
freopen("necklace.in","r",stdin);
freopen("necklace.out","w",stdout);
scanf("%s%s",s+1,t+1);
ns=strlen(s+1),nt=strlen(t+1);
Work(0);
reverse(t+1,t+nt+1);
Work(1);
printf("%d\n%d %d\n",ans,ps,pt);
}