[Codeforces.666A.Reberland Linguistics(DP)]

15484 단어 Codeforce#소박한 DP

제목 링크: 전송문


제목:


주어진 꿰미 s는 하나의 기본 꿰미 뒤에 임의의 여러 개의 길이가 2 또는 3인 접미사로 구성되어 있으며 기본 꿰미의 길이가 >4이고 인접한 접미사가 같지 않습니다.기본 직렬이 임의로 확정된 상황에서 가능한 모든 접미사 직렬을 구합니다.

아이디어:


dp[i][0]dp[i][0]dp[i][0]는 제a[i-1]a[i-1]a[i-1]~a[i]a[i]a[i]a[i]로 구성된 문자열이 가능한지, dp[i][1]dp[i][1]dp[i][1]는 제a[i-4]a[i-2]a[i-4]a[i]a[i]a[i]a[i]a[i]a[i]a[i]a[i]a[i]a[i]a[i]로 구성된 문자열이 가능한지를 나타낸다.
마지막 두 개의 길이가 2인 접미사와 길이가 3인 접미사를 선택할 수 있다면 가능합니다.
​ d p [ i ] [ 0 ] = ( d p [ i + 2 ] [ 0 ] & & s 1 ! = s 2 )    ∣ ∣    d p [ i + 3 ] [ 1 ] dp[i][0]=(dp[i+2][0]\&\&s1!=s2)~~||~~dp[i+3][1] dp[i][0]=(dp[i+2][0]&&s1!=s2)  ∣∣  dp[i+3][1]
​ d p [ i ] [ 1 ] = d p [ i + 2 ] [ 0 ]    ∣ ∣    ( d p [ i + 3 ] [ 1 ] & & s 1 ! = s 2 ) dp[i][1]=dp[i+2][0]~~||~~(dp[i+3][1]\&\&s1!=s2) dp[i][1]=dp[i+2][0]  ∣∣  (dp[i+3][1]&&s1!=s2) 
#include
#define mset(a,b) memset(a,b,sizeof(a))
#define x  first
#define y  second
using  namespace std;
typedef long long ll;
typedef  pair<int,int> _p;
const int MAX=100000;
const int inf=0x3f3f3f3f;
const double EPS=1e-10;
const int MOD=1e9+7;
int dp[10005][2];/*0 :2 ,1:3*/
set<string> mmp;
int main()
{
    string s;
    cin>>s;
    if(s.length()<6)
    {
        puts("0");
        return 0;
    }
    int ls=s.length();
    if(ls>6)
    {
        dp[ls-1][0]=1;
        mmp.insert(s.substr(ls-2,2));
    }
    if(ls>7)
    {
        dp[ls-1][1]=1;
        mmp.insert(s.substr(ls-3,3));
    }
    dp[ls-2][0]=dp[ls-2][1]=0;
    for(int i=ls-3; i>=4; --i)
    {
        if(i-2>=4)
        {
            if((i+3<ls&&dp[i+3][1]) || (dp[i+2][0]&&s.substr(i-1,2)!=s.substr(i+1,2) )) //0
            {
                dp[i][0]=1;
                mmp.insert(s.substr(i-1,2));
            }
        }
        if(i-3>=4)
        {
            if(dp[i+2][0]>0||( i+3<ls &&dp[i+3][1]&&s.substr(i-2,3)!=s.substr(i+1,3))) // 1
            {
                dp[i][1]=1;
                mmp.insert(s.substr(i-2,3));
            }
        }

    }
    cout<<mmp.size()<<endl;
    for(auto i:mmp)
        cout<<i<<endl;
    return 0;
}
AmazonBI 서비스 QuickSight를 만져봤습니다!
[React] 클래스형 컴포넌트 vs 함수형 컴포넌트

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage