tyvj1102 单词的划分

时间：2022-02-17 00:17:22

描述

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。

输入格式

第一行，一个字符串。（字符串的长度不超过100）
第二行一个整数n，表示单词的个数。（n<=100）
第3~n+2行，每行列出一个单词。

输出格式

一个整数，表示字符串可以被划分成的最少的单词数。

测试样例1

输入

realityour 
5 
real 
reality 
it 
your 
our

输出

2

备注

（原字符串可拆成real+it+your或reality+our，由于reality+our仅为两个部分，因此最优解为2，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用）
#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int sed = ,Sed = ,mod = ,Mod = ;

int n,m,dp[];

string a[],s;

vector<int> h[mod];

int main(){

    cin>>s>>n;

    for(int i = ;i <= n;i++){

        cin>>a[i];

        int hash = ,Hash = ;

        for(int j = ;j < a[i].size();j++){

            hash = (hash * sed + a[i][j]) % mod;

            Hash = (Hash * Sed + a[i][j]) % Mod;

        }

        h[hash].push_back(Hash);

    }

    m = s.size();

    for(int i = ;i <= m;i++) dp[i] = ;

    for(int i = ;i <= m;i++){

        for(int j = i;j >= ;j--){

            int hash = ,Hash = ;

            for(int k = j - ;k <= i - ;k++){

                hash = (hash * sed + s[k]) % mod;

                Hash = (Hash * Sed + s[k]) % Mod;

            }

            bool ok = false;

            for(int k = ;k < h[hash].size();k++){

                if(h[hash][k] == Hash){

                    ok = true;

                    break;

                }

            }

            if(ok) dp[i] = min(dp[i],dp[j-] + );

        }

    }

    cout<<dp[m];

    return ;

}

相关文章