単語の区分

単語の区分
                        Time Limit:1000MS Memory Limit:30000KB
Descriptionには長い小文字からなる文字列があります.この文字列の解析を容易にするためには,各部分を1つの単語と呼ぶいくつかの部分に分割する必要がある.分析量を減らす目的で,分割した単語数が少ないほどよいと考えられる.あなたはこの仕事を完成しに来ました.
Inputの第1の挙動は整数Tであり、T組のテストデータがあることを示す.各テストデータの最初の動作をテストする文字列.(長さが256未満)第2の挙動の整数N.(1<=N<=100)以下のN行は、1行につき1単語であり、各単語の長さは128未満である.
Outputはテストデータのセットごとに1行を占め、この行には整数が1つしかなく、文字列が分割できる最小の単語数を表しています.私たちは単語が区別できることを保証します.
Sample Input  1 realityour 5 real reality it your our
Sample Output  2
この問題は比較の基礎の動的計画問題(DP)で、DPは1種の思想で、よく最適化問題を解くために用いられて、動的計画で最適化問題を解く第1歩は最適解の構造を描くことで、具体的に《アルゴリズムの導論》を参照して、動的計画の核心は状態の移動方程式で、状態の移動方程式を書くことができる限り、問題は基本的に解決しました.この問題を例に,この問題の状態遷移方程式をどのように得るかを見た.この問題は分割を求める最小小数であり,f(i)は長さiの文字列が分割される最小単語数であり,f(0)=0であると仮定する.では、f(i)=min(f(i)、f(i-length(w)+1)であり、wは所定の辞書の単語を表す.f(i-length(w)+1が分からないかもしれませんが、説明します.与えられたテスト例を例に挙げます.
文字列S
図に示すように、i=4の場合、文字列Sの最初の単語であるため、前の単語は実際には存在せず、f(0)として指定する単語realが一致する.したがって、f(4)=min(f(4)、f(4-一致する単語長)+1)となる.i=6の場合、また単語itが一致するので、f(6)=min(f(6)、f(6-2)+1)である.図に示すように、
状態遷移とは,前の状態から現在の状態に遷移することである.つまり文字列realitの最小区分数の前の状態はrealの最小区分数+1で、見ている学生はよく体得することができます.コードを貼り付けます.

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;


int com(string s, int pos, string s2)
{
    int index = pos-1;
    for(int i = s2.length()-1; i >= 0; --i)
    {
        if(s2[i] != s[index--])
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int num;
    cin >> num;
    int f[300];
    while(num--)
    {
        f[0] = 0;
        for(int i = 1; i < 300; ++i)
        {
            f[i] = 1000000;
        }
        string s;
        cin >> s;
        int n;
        cin >> n;
        vector<string> v;
        for(int i = 0; i < n; ++i)
        {
            string str;
            cin >> str;
            v.push_back(str);
        }
        for(int i = 1; i <= (int)s.length(); ++i)
        {
            for(int j = 0; j <(int)v.size(); ++j)
            {
                int length = v[j].length();
                if(i < length)
                {
                    continue;
                }
                else if(com(s,i,v[j]))
                {
                    f[i] = min(f[i],f[i-length]+1);
                    //cout << "f[" << i << "]    " << f[i] << endl;
                }
            }
        }
        cout << f[s.length()] << endl;
    }
    return 0;
}