題意：
求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);
}