[bzoj4060] [Cerc2012] Word equations 문자열
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define maxn 4207
inline int rd() {
char c = getchar();
while (!isdigit(c)) c = getchar() ; int x = c - '0';
while (isdigit(c = getchar())) x = x * 10 + c - '0';
return x;
}
char _p[maxn][7];
int _l[maxn] , tot;
struct Trie {
int ch[maxn][26];
int val[maxn];
int _upcase , sz;
inline int idx(char c) {
if (_upcase) return c - 'A';
else return c - 'a';
}
void init(int t) {
memset(ch[0] , 0 , sizeof ch[0]);
_upcase = t;
sz = 1 , tot = 0;
}
int get(char*s , int n) {
int u = 0;
rep (i , 1 , n) {
int c = idx(s[i]);
if (!ch[u][c]) {
val[sz] = 0 , memset(ch[sz] , 0 , sizeof ch[sz]);
ch[u][c] = sz ++;
}
u = ch[u][c];
}
if (!val[u]) {
val[u] = ++ tot;
if (!_upcase) {
rep (i , 1 , n)
_p[tot][i] = s[i];
_p[tot][n + 1] = '\0';
_l[tot] = n;
}
}
return val[u];
}
}large , small;
char tmp[maxn] , str[maxn] , tar[maxn];
int K , mark[maxn] , lc[maxn] , rc[maxn] , n , p , st , f[maxn / 4][maxn] , vis[maxn];
void read_str() {
int t = 0 , l1 = 0 , r1 = 0 , r2 = 0;
for (char c = getchar();c != '
';c = getchar()) {
if (c == ' ') c = getchar();
if (c == '=')
l1 = large.get(tmp , t) , t = 0;
else if (c == '+')
r1 = large.get(tmp , t) , t = 0;
if (isalpha(c)) tmp[++ t] = c;
}
if (!r1) {
r1 = small.get(tmp , t);
lc[l1] = r1;
mark[r1] = 1;
} else {
r2 = large.get(tmp , t);
lc[l1] = r1 , rc[l1] = r2;
}
}
void input() {
rep (i , 0 , tot) rep(j , 0 , n + 1) f[i][j] = 0;
rep (i , 0 , tot) mark[i] = lc[i] = rc[i] = vis[i] = 0;
scanf("%d
" , &K);
large.init(1) , small.init(0);
rep (i , 1 , K)
read_str();
scanf("%s" , str + 1);
scanf("%s" , tar + 1);
n = strlen(tar + 1);
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = 1;
if (!u) return;
if (mark[lc[u]]) {
int v = u , u = lc[v];
rep (i , 1 , n + 1) {
int j = i;
rep (k , 1 , _l[u])
if (j > n)
break;
else if (_p[u][k] == tar[j])
j ++;
f[v][i] = j;
}
} else {
dfs(lc[u]) , dfs(rc[u]);
rep (i , 1 , n + 1)
f[u][i] = f[rc[u]][f[lc[u]][i]];
}
}
void solve() {
st = large.get(str , strlen(str + 1));
dfs(st);
if (f[st][1] > n)
puts("YES");
else
puts("NO");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.txt" , "r" , stdin);
#endif
per (T , rd() , 1) {
input();
solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.