【做题】sgu189 Perl-like Substr——dark模拟

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Perl›Perl教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

注：这篇博客纯属为凑篇数而生。

题面较长，幸运的是，网上给出了相当不错的翻译。

需要支持的操作很简单，即对子串提取、赋值和输出，且对时间复杂度没有要求。换言之此题有成为块链毒瘤题的潜质。难点在于输入的格式是类似于源代码的，但形式单一，变量前均有$字符标注，可以通过直接判断来解决。于是就只需要大力讨论就可以了。

这或许就是所谓的题意即题解吧。

时间复杂度O(m*l)。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int N = 110, LN = 25;
  4 string var[N], tmp, tp;
  5 int node[N * LN][63], tag[N * LN], cnt, tot = 1, pos;
  6 inline int read() {
  7   int res = 0; bool key = 0;
  8   for (; !(tmp[pos] >= '0' && tmp[pos] <= '9') ; ++ pos)
  9     key = (tmp[pos] == '-');
 10   for (; tmp[pos] >= '0' && tmp[pos] <= '9' ; ++ pos)
 11     res = (res << 3) + (res << 1) + tmp[pos] - '0';
 12   if (key) res = - res;
 13   return res;
 14 }
 15 inline int get_val(char x) {
 16   if (x >= '0' && x <= '9') return x - '0';
 17   if (x >= 'a' && x <= 'z') return x - 'a' + 10;
 18   if (x >= 'A' && x <= 'Z') return x - 'A' + 36;
 19   return -1;
 20 }
 21 inline bool invar(char x) {
 22   return (x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || \
 23     (x >= 'A' && x <= 'Z') || x == ' ' || x == ',' || x == '.' || \
 24     x == '-' || x == '_' || x == ':' || x == '!' || x == '?';
 25 }
 26 int find(string s) {
 27   int l = s.length(), p = 1, t;
 28   for (int i = 0 ; i < l ; ++ i) {
 29     t = get_val(s[i]);
 30     if (!node[p][t]) node[p][t] = ++ tot;
 31     p = node[p][t];
 32   }
 33   if (!tag[p]) {
 34       tag[p] = ++ cnt;
 35       var[cnt] = "";
 36     }
 37   return tag[p];
 38 }
 39 int get_tag() {
 40   tp = "";
 41   while (~get_val(tmp[++ pos]))
 42     tp += tmp[pos];
 43   return find(tp);
 44 }
 45 void solve_init() {
 46   int l = tmp.length(), p;
 47   tp = "";
 48   for (pos = 0 ; pos < l ; ++ pos) {
 49     if (tmp[pos] == '$') {
 50       var[p = get_tag()] = "";    
 51       break;
 52     }
 53   }
 54   while (tmp[pos] != '"') ++ pos;
 55   for (++ pos ; invar(tmp[pos]) ; ++ pos) {
 56     var[p] += tmp[pos];
 57   }
 58 }
 59 void subst(int& p,int& l,int& n) {
 60   while (tmp[pos] != '$') ++ pos;
 61   p = get_tag();
 62   int len = var[p].length(), be, co;
 63   be = read();
 64   while (tmp[pos] != ',' && tmp[pos] != ')') ++ pos;
 65   if (tmp[pos] == ')') co = 0;
 66   else co = read();
 67   l = be >= 0 ? be : len + be;
 68   n = co >= 0 ? co > 0 ? co : len - l : len + co - l;
 69   while (tmp[pos] != ')') ++ pos;
 70   ++ pos;
 71 }
 72 void print() {
 73   while (tmp[pos] != '$' && tmp[pos] != 's') ++ pos;
 74   int p,l,n;
 75   if (tmp[pos] == '$') {
 76     p = get_tag();
 77     cout << var[p] << endl;
 78   } else {
 79     subst(p,l,n);
 80     cout << var[p].substr(l,n) << endl;
 81   }
 82   while (tmp[pos] != ')') ++ pos;
 83   ++ pos;
 84 }
 85 void solve() {
 86   int l = tmp.length(), p1, p2, l1, n1, l2, n2, t1, t2;
 87   for (pos = 0 ; tmp[pos] == ' ' ; ++ pos);
 88   switch(tmp[pos]) {
 89   case 's':subst(p1,l1,n1), t1 = 1; break;
 90   case 'p':print(); return;
 91   case '$':p1 = get_tag(), t1 = 0; break;
 92   }
 93   for (; tmp[pos] != '$' && tmp[pos] != 's' ; ++ pos);
 94   switch(tmp[pos]) {
 95   case 's':subst(p2,l2,n2), t2 = 1; break;
 96   case '$':p2 = get_tag(), t2 = 0; break;
 97   }
 98   if ((!t1) && (!t2)) var[p1] = var[p2];
 99   else if ((!t1) && t2) var[p1] = var[p2].substr(l2,n2);
100   else if (t1 && (!t2)) var[p1].replace(l1,n1,var[p2]);
101   else if (t1 && t2) var[p1].replace(l1,n1,var[p2],l2,n2);
102 }
103 int main() {
104   int n,m;
105   scanf("%d%d\n",&n,&m);
106   for (int i = 1 ; i <= n ; ++ i) {
107     getline(cin,tmp);
108     solve_init();
109   }
110   for (int i = 1 ; i <= m ; ++ i) {
111     getline(cin,tmp);
112     solve();
113   }
114   return 0;
115 }