本文共 1729 字，大约阅读时间需要 5 分钟。
$dp$。
题意中有一个词组：$in$ $a$ $row$，是连续的意思....
因此这题只要倒着$dp$一下就可以了。$f[i][0]$表示从$i$位置往后割两个能否割，$f[i][1]$表示从$i$位置往后割三个能否割。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}}const int maxn=100100;char s[maxn];int len,f[maxn][2];vector ans;map d;int main(){ memset(s,0,sizeof s); scanf("%s",s); len=strlen(s); f[len][0]=f[len][1]=1; for(int i=len-1;i>4;i--) { if(len-i>=2) { if(f[i+2][1]==1) { char t[5]; memset(t,0,sizeof t); t[0]=s[i]; t[1]=s[i+1]; f[i][0]=1; if(d[t]==0) ans.push_back(t),d[t]=1; } else if(f[i+2][0]==1) { char t[5],g[5]; memset(t,0,sizeof t); memset(g,0,sizeof g); t[0]=s[i]; t[1]=s[i+1]; g[0]=s[i+2]; g[1]=s[i+3]; if(strcmp(t,g)==0) continue; f[i][0]=1; if(d[t]==0) ans.push_back(t),d[t]=1; } } if(len-i>=3) { if(f[i+3][0]==1) { char t[5]; memset(t,0,sizeof t); t[0]=s[i]; t[1]=s[i+1]; t[2]=s[i+2]; f[i][1]=1; if(d[t]==0) ans.push_back(t),d[t]=1; } else if(f[i+3][1]==1) { char t[5],g[5]; memset(t,0,sizeof t); memset(g,0,sizeof g); t[0]=s[i]; t[1]=s[i+1]; t[2]=s[i+2]; g[0]=s[i+3]; g[1]=s[i+4]; g[2]=s[i+5]; if(strcmp(t,g)==0) continue; f[i][1]=1; if(d[t]==0) ans.push_back(t),d[t]=1; } } } sort(ans.begin(),ans.end()); printf("%d\n",ans.size()); for(int i=0;i
转载于:https://www.cnblogs.com/zufezzt/p/5874458.html