ソースコード
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
#define FAIL 0
#define SUCCESS 1
#include <ctype.h>
typedef string::const_iterator State;
uint32_t xor128(void) {
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;
uint32_t t;
t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
vector<string> expression(State &begin);
string s;
vector<vector<string>> inputs;
vector<string> loop(State &begin) {
vector<vector<string>> ans;
for (; begin != s.end();) {
if (*begin == '*') {
vector<string> tmp = ans[ans.size() - 1];
ans.pop_back();
vector<string> a, b;
a.push_back("split 1 " + to_string(tmp.size() + 2));
ans.push_back(a);
ans.push_back(tmp);
b.push_back("jmp " + to_string(-((int)tmp.size() + 1)));
ans.push_back(b);
begin++;
}
else if (*begin == '?') {
vector<string> tmp = ans[ans.size() - 1];
ans.pop_back();
vector<string> a;
a.push_back("split 1 " + to_string(tmp.size() + 1));
ans.push_back(a);
ans.push_back(tmp);
begin++;
}
else if (*begin == '+') {
vector<string> a;
a.push_back("split 1 " + to_string(-(int)ans[ans.size() - 1].size()));
ans.push_back(a);
begin++;
}
else if (*begin == '(') {
begin++;
vector<string> a = expression(begin);
ans.push_back(a);
}
else if (*begin == ')') {
break;
}
else if (*begin == '|') {
break;
}
else if(*begin == '['){
string p = "";
begin++;
while(*begin != ']'){
p.push_back(*begin);
begin++;
}
begin++;
vector<char> going;
for(int i = 0;i < p.length();++i){
if(i >= p.length()-2||p[i+1] != '-'){
going.push_back(p[i]);
}else{
for(char q = p[i];q <= p[i+2];++q){
going.push_back(q);
}
i++;
}
}
if(going.empty() == false){
string pushing = "(";
pushing.push_back(going[0]);
for(int i = 1;i < going.size();++i){
pushing += "|";
pushing.push_back(going[i]);
}
pushing += ")";
State beginner = pushing.begin();
beginner++;
vector<string> a = expression(beginner);
ans.push_back(a);
}
}
else{
vector<string> a;
string b = "char ";
b.push_back(*begin);
a.push_back(b);
ans.push_back(a);
begin++;
}
}
vector<string> final_ans;
for (int i = 0; i < ans.size(); ++i) {
REP(q, ans[i].size()) final_ans.push_back(ans[i][q]);
}
return final_ans;
}
vector<string> expression(State &begin) {
vector<vector<string>> ans;
ans.push_back(loop(begin));
for (; begin != s.end();) {
if (*begin == ')') {
begin++;
break;
}else if(*begin == '('){
ans.push_back(loop(begin));
continue;
}
begin++;
vector<string> tmp = loop(begin);
vector<string> backing = ans[ans.size() - 1];
ans.pop_back();
vector<string> a;
a.push_back("split 1 " + to_string(backing.size() + 2));
REP(i,backing.size()){
a.push_back(backing[i]);
}
a.push_back("jmp " + to_string(tmp.size() + 1));
REP(i,tmp.size()){
a.push_back(tmp[i]);
}
ans.push_back(a);
}
vector<string> final_ans;
for (int i = 0; i < ans.size(); ++i) {
REP(q, ans[i].size()) final_ans.push_back(ans[i][q]);
}
return final_ans;
}
vector<string> compiler() {
cin >> s;
int check_required = 0;
if(s[s.length()-1] == '$'){
check_required = 1;
s.pop_back();
}
int first_day = 0;
if(s[0] == '^'){
first_day = 1;
s.erase(s.begin());
}
State begin = s.begin();
vector<string> ans = expression(begin);
if(check_required == 0){
ans.push_back("match");
}else{
ans.push_back("ifmatch");
}
if(first_day == 1){
ans.insert(ans.begin(),"start");
}
return ans;
}
long long ok[10000][10000] = {};
int solve(int start) {
queue<pair<int,int>> next;
next.push(make_pair(start,0));
while(next.empty() == false){
int SP = next.front().first,PC = next.front().second;
next.pop();
if(ok[SP][PC]){
if(ok[SP][PC] == 2)
return 2;
continue;
}
if (inputs[PC][0] == "match"){
return 2;
}
if(inputs[PC][0] == "ifmatch"){
if(SP == s.length()) return 2;
}
if (inputs[PC][0] == "char") {
if (s.length() <= SP) continue;
if (s[SP] != inputs[PC][1][0]) continue;
ok[SP][PC] = 1;
next.push(make_pair(SP+1,PC+1));
}
if (inputs[PC][0] == "jmp") {
ok[SP][PC] = 1;
next.push(make_pair(SP,PC+stoll(inputs[PC][1])));
}
if (inputs[PC][0] == "split") {
ok[SP][PC] = 1;
if(xor128() % 2 == 1){
next.push(make_pair(SP,PC+stoll(inputs[PC][2])));
next.push(make_pair(SP,PC+stoll(inputs[PC][1])));
}else{
next.push(make_pair(SP,PC+stoll(inputs[PC][1])));
next.push(make_pair(SP,PC+stoll(inputs[PC][2])));
}
}
}
return 1;
}
int main(){
stringstream foooa;
vector<string> bytecode = compiler();
for(int i = 0;i < bytecode.size();++i){
foooa << bytecode[i] << endl;
}
int bobo = 0;
while(bobo < bytecode.size()){
vector<string> hogea;
string tmp;
foooa >> tmp;
hogea.push_back(tmp);
bobo++;
if(hogea[0] == "char"){
foooa >> tmp;
hogea.push_back(tmp);
}
else if(hogea[0] == "split"){
foooa >> tmp;
hogea.push_back(tmp);
foooa >> tmp;
hogea.push_back(tmp);
}
else if(hogea[0] == "jmp"){
foooa >> tmp;
hogea.push_back(tmp);
}
inputs.push_back(hogea);
}
cin >> s;
if(inputs[0][0] == "start"){
inputs.erase(inputs.begin());
if(solve(0) == 2){
cout << 0 << endl;
}else{
cout << -1 << endl;
}
}else{
for(int i = 0;i < s.length();++i){
if(solve(i) == 2){
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
return 0;
}