白準-16500文字列判別


質問する
単語リストAの複数の単語をつづり、文字列Sを作成できるか否かを求める.
の意見を打診
タイムアウト
文字列の前半に一致する単語のリストを表示します.
一致する場合は、前の部分以外にも後ろの部分ができるかどうかをチェックします.
void canMake(string s) { //s를 단어 목록에서 만들 수 있는지 검사하는 함수
    for (int i = 0; i < n; i++) { //단어 목록을 돌면서
        bool f = true;
        for (int j = 0; j < word[i].size(); j++) {
            if (word[i][j] != s[j]) {
                f = false;
                break;
            }
        }
        if (f) { //i번째 단어의 모든 부분이 일치하면
            if (word[i].size() == s.size()) {
                result = 1; //크기가 같으면 s를 다 만들었음
            }else{
                canMake(s.substr(word[i].size()));
                //뒤에 남은 부분이 있으면 다시 만들 수 있는지 검사
            }
        }
    }
}
タイムアウトします
間違いない.
問題検索では、単語リストにsubstringがある場合.
助けて助けて助けて...だからタイムアウトします.
たとえば、ソフトウェア、ソフトウェア、ソフトウェア、コンテストなどです.
ソフトウェア、contest、またはソフトウェア、contestなどの使用
サブストリングがあると、いろいろなことが起こり、繰り返し検査されたり、問題が発生したりします
しかし、私は100個の単語リストAの長さが100以下です.
例が長くても、時間を超えないと思います.
aaaaaaaaaaaaaaaaaaaaaa...
8
aa
aaa
aaaa
...
このような例であれば、問題になるかもしれない.思いついた
だから私はもう一つの組み合わせをして、検査を避けたいです.
前からiの長さのsubstringは、以前に作成したサブ文字列を保存しようとします.
check配列の作成
上記と同じsubstringが作成された場合
check[i]値を1に変更
次にstringをチェックすると
check[string.size()]値は1です.
もう検査しないようにした
コード#コード#
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int n, flag;

string word[105];
int check[105];

void canMake(string s) {
	if (check[s.size()] != 1) {
		if (flag != 1) {
			for (int i = 0; i < n; i++) {
				bool f = true;
				for (int j = 0; j < word[i].size(); j++) {
					if (word[i][j] != s[j]) {
						f = false;
						break;
					}
				}
				if (f) {
					if (word[i].size() == s.size()) {
						flag = 1;
					}
					check[s.size()] = 1;
					canMake(s.substr(word[i].size()));
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	string s;
	cin >> s >> n;

	for (int i = 0; i < n; i++) {
		cin >> word[i];
	}

	canMake(s);

	cout << flag;

	return 0;
}