网站 建设app,长沙网络营销 公司,乐清信息网,android官网下载正题
题目链接:https://www.luogu.com.cn/problem/P3181 题目大意
两个字符串#xff0c;求有多少个(l1,r1,l2,r2)(l_1,r_1,l_2,r_2)(l1,r1,l2,r2)使得字符串l1∼r1l_1\sim r_1l1∼r1的子串与l2∼r2l_2\sim r_2l2∼r2的子串相等。 解题思路 SAMSAMSAM做法
…正题
题目链接:https://www.luogu.com.cn/problem/P3181 题目大意
两个字符串求有多少个(l1,r1,l2,r2)(l_1,r_1,l_2,r_2)(l1,r1,l2,r2)使得字符串l1∼r1l_1\sim r_1l1∼r1的子串与l2∼r2l_2\sim r_2l2∼r2的子串相等。 解题思路
SAMSAMSAM做法
又是公共子串的问题我们先对第一个串构造出SAMSAMSAM然后用第二个串在第一个串上跑。·对于每个前缀我们有一个当前节点xxx和一个最长匹配长度lll。处理处每一个位置的endposendposendpos大小fxf_xfx
在节点xxx的endposendposendpos类中长度不超过lll的都是这个前缀的一个后缀那么会产生贡献(l−lenx)∗fx(l-len_x)*f_x(l−lenx)∗fx。然后xxx的祖先上的所有endposendposendpos类也是这个前缀的后缀定义gxg_xgx表示xxx极其所有祖先的fx∗(lenx−lenfax)f_x*(len_x-len_{fa_x})fx∗(lenx−lenfax)的和那么再有贡献是gfaxg_{fa_x}gfax
时间复杂度O(n)O(n)O(n)
SASASA做法
依旧是拼接后求SASASA然后对于一个原来在BBB串处的后缀如果和另一个AAA串的LCPLCPLCP为xxx那么就会产生xxx的贡献然后直接用一个数据结构维护即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510;
ll n,f[N],g[N],c[N],rk[N],ans;
ll last,cnt,len[N],ch[N][26],fa[N];
char s[N];
void Ins(ll c){ll plast,nplastcnt;len[np]len[p]1;f[np]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{ll qch[p][c];if(len[p]1len[q])fa[np]q;else{ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]fa[np]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return;
}
int main()
{lastcnt1;scanf(%s,s);nstrlen(s);for(ll i0;in;i)Ins(s[i]-a);scanf(%s,s);nstrlen(s);for(ll i1;icnt;i)c[len[i]];for(ll i1;in;i)c[i]c[i-1];for(ll i1;icnt;i)rk[c[len[i]]--]i;for(ll icnt;i1;i--)f[fa[rk[i]]]f[rk[i]];for(ll i1;icnt;i){int xrk[i];g[x]g[fa[x]]f[x]*(len[x]-len[fa[x]]);}ll x1,l0;for(ll i0;in;i){ll cs[i]-a;if(ch[x][c])xch[x][c],l;else{while(x!ch[x][c])xfa[x];if(!x)x1,l0;else llen[x]1,xch[x][c];}ansf[x]*(l-len[fa[x]])g[fa[x]];}printf(%lld,ans);return 0;
}
