{"id":569,"date":"2012-11-16T13:34:51","date_gmt":"2012-11-16T05:34:51","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=569"},"modified":"2012-11-17T17:30:10","modified_gmt":"2012-11-17T09:30:10","slug":"rosalind-1","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/rosalind-1\/","title":{"rendered":"Rosalind 1"},"content":{"rendered":"

http:\/\/rosalind.info\/problems\/as-graph\/<\/a>
\nhttp:\/\/en.wikipedia.org\/wiki\/Bioinformatics<\/a><\/p>\n

<\/p>\n

\u5b57\u7b26\u4e32\u5904\u7406\u3001\u6b63\u5219\u8868\u8fbe\u5f0f<\/h3>\n
\r\ns = gets\r\nprint [s.count('A'), s.count('C'), s.count('G'), s.count('T')] * ' '\r\n<\/pre>\n
\r\nprint gets.gsub('T','U')\r\n<\/pre>\n
\r\ns = gets\r\ns.gsub!('A','a'); s.gsub!('T','A'); s.gsub!('a','T')\r\ns.gsub!('C','c'); s.gsub!('G','C'); s.gsub!('c','G')\r\nprint s.reverse\r\n<\/pre>\n
\r\n$buf = gets()\r\n\r\ndef gc(s)\r\n\tgcc = 0.0\r\n\ts.each_char{|si|\t\t\r\n\t\tgcc += 1 if (si == 'G' || si == 'C') \r\n\t}\r\n\treturn gcc \/ s.size\r\nend\r\n\r\ndef getdna()\r\n\tdna = gets().chomp\r\n\tdna += $buf.chomp while ($buf = gets()) && ($buf[0] != '>')\t\r\n\treturn dna\r\nend\r\n\r\ndna = "$"\r\n\r\nwhile $buf do\r\n\t_id, _dna = $buf[1..-1], getdna()\t\t\r\n\tid, dna = _id, _dna if gc(_dna) > gc(dna)\r\nend\r\n\r\nputs id\r\nprint gc(dna) * 100, '%'\r\n<\/pre>\n
\r\ns = gets.chomp; t = gets.chomp; dist = 0\r\n0.upto(s.size-1){|i|\r\n\tdist += 1 if s[i] != t[i]\t\t\r\n}\r\np dist\r\n<\/pre>\n
\r\ns = gets.chomp; n = s.length; a = Array.new(n){Hash.new(0)}\r\n\r\nbegin\t\r\n\t0.upto(n-1){|i|\r\n\t\ta[i][s[i]] += 1\r\n\t}\r\nend while s = gets\r\n\r\n\r\ndef scan(a, n, ch)\r\n\tprint ch,':'\r\n\t0.upto(n-1){|i|\r\n\t\tprint ' ', a[i][ch]\r\n\t}\r\n\tputs\r\nend\r\n\r\n\r\ndef common(ai)\r\n\treturn 'A' if (ai['A'] >= ai['C'] && ai['A'] >= ai['G'] && ai['A'] >= ai['T']) \t\r\n\treturn 'C' if (ai['C'] >= ai['A'] && ai['C'] >= ai['G'] && ai['C'] >= ai['T']) \r\n\treturn 'G' if (ai['G'] >= ai['A'] && ai['G'] >= ai['C'] && ai['G'] >= ai['T']) \r\n\treturn 'T'\r\nend\r\n\r\na.each{|ai|\r\n\t#ai.sort_by{|key, value| value}\r\n\t#print ai.begin().value\r\n\tprint common(ai)\r\n}\t\r\nputs\r\n\r\n\t\t\r\nscan(a, n, 'A'); scan(a, n, 'C'); scan(a, n, 'G'); scan(a, n, 'T')\r\n<\/pre>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 1009;\r\n\r\npair<string, string> A[N];\r\nint n;\r\n\r\nbool adj(string a, string b, int k){\r\n    if (a == b) return false;\r\n    REP(i, k) if (a[SZ(a)-k+i] != b[i]) return false;\r\n    return true;\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    string id, dna; cin >> id; while (id[0] == '>'){\r\n        ERS(id, 0), A[n].fi = id, CLR(dna);\r\n        while (cin >> id && id[0] != '>') dna += id;\r\n        A[n++].se = dna;\r\n    }\r\n\r\n    REP_2(i, j, n, n) if (adj(A[i].se, A[j].se, 3)){\r\n        cout << A[i].fi << " " << A[j].fi << endl;\r\n    }\r\n}\r\n<\/pre>\n
\r\ndict = {\r\n    'UCA' => 'S',    # Serine\r\n    'UCC' => 'S',    # Serine\r\n    'UCG' => 'S',    # Serine\r\n    'UCU' => 'S',    # Serine\r\n    'UUC' => 'F',    # Phenylalanine\r\n    'UUU' => 'F',    # Phenylalanine\r\n    'UUA' => 'L',    # Leucine\r\n    'UUG' => 'L',    # Leucine\r\n    'UAC' => 'Y',    # Uyrosine\r\n    'UAU' => 'Y',    # Uyrosine\r\n    'UAA' => '_',    # Stop\r\n    'UAG' => '_',    # Stop\r\n    'UGC' => 'C',    # Cysteine\r\n    'UGU' => 'C',    # Cysteine\r\n    'UGA' => '_',    # Stop\r\n    'UGG' => 'W',    # Uryptophan\r\n    'CUA' => 'L',    # Leucine\r\n    'CUC' => 'L',    # Leucine\r\n    'CUG' => 'L',    # Leucine\r\n    'CUU' => 'L',    # Leucine\r\n    'CCA' => 'P',    # Proline\r\n    'CCC' => 'P',    # Proline\r\n    'CCG' => 'P',    # Proline\r\n    'CCU' => 'P',    # Proline\r\n    'CAC' => 'H',    # Histidine\r\n    'CAU' => 'H',    # Histidine\r\n    'CAA' => 'Q',    # Glutamine\r\n    'CAG' => 'Q',    # Glutamine\r\n    'CGA' => 'R',    # Arginine\r\n    'CGC' => 'R',    # Arginine\r\n    'CGG' => 'R',    # Arginine\r\n    'CGU' => 'R',    # Arginine\r\n    'AUA' => 'I',    # Isoleucine\r\n    'AUC' => 'I',    # Isoleucine\r\n    'AUU' => 'I',    # Isoleucine\r\n    'AUG' => 'M',    # Methionine\r\n    'ACA' => 'T',    # Uhreonine\r\n    'ACC' => 'T',    # Uhreonine\r\n    'ACG' => 'T',    # Uhreonine\r\n    'ACU' => 'T',    # Uhreonine\r\n    'AAC' => 'N',    # Asparagine\r\n    'AAU' => 'N',    # Asparagine\r\n    'AAA' => 'K',    # Lysine\r\n    'AAG' => 'K',    # Lysine\r\n    'AGC' => 'S',    # Serine\r\n    'AGU' => 'S',    # Serine\r\n    'AGA' => 'R',    # Arginine\r\n    'AGG' => 'R',    # Arginine\r\n    'GUA' => 'V',    # Valine\r\n    'GUC' => 'V',    # Valine\r\n    'GUG' => 'V',    # Valine\r\n    'GUU' => 'V',    # Valine\r\n    'GCA' => 'A',    # Alanine\r\n    'GCC' => 'A',    # Alanine\r\n    'GCG' => 'A',    # Alanine\r\n    'GCU' => 'A',    # Alanine\r\n    'GAC' => 'D',    # Aspartic Acid\r\n    'GAU' => 'D',    # Aspartic Acid\r\n    'GAA' => 'E',    # Glutamic Acid\r\n    'GAG' => 'E',    # Glutamic Acid\r\n    'GGA' => 'G',    # Glycine\r\n    'GGC' => 'G',    # Glycine\r\n    'GGG' => 'G',    # Glycine\r\n    'GGU' => 'G'    # Glycine    \r\n};\r\n\r\nmRNA = gets.chomp\r\nputs mRNA.gsub(\/\\w{3}\/).each(&dict.method(:[]))[0..-1].gsub(\/_.*\/, '')\r\n<\/pre>\n
\u3002\u3002\u3002mRNA<\/a>\u3001\u86cb\u767d\u8d28\uff08Protein\uff09<\/a>\u3001\u6c28\u57fa\u9178\uff08Amino Acid\uff09<\/a>\u3001\u5bc6\u7801\u5b50\uff08Genetic Code\uff09<\/a>\u3002\u3002\u3002<\/p>\n
\r\ndict = {\r\n    'TCA' => 'S',    # Serine\r\n    'TCC' => 'S',    # Serine\r\n    'TCG' => 'S',    # Serine\r\n    'TCT' => 'S',    # Serine\r\n    'TTC' => 'F',    # Phenylalanine\r\n    'TTT' => 'F',    # Phenylalanine\r\n    'TTA' => 'L',    # Leucine\r\n    'TTG' => 'L',    # Leucine\r\n    'TAC' => 'Y',    # Tyrosine\r\n    'TAT' => 'Y',    # Tyrosine\r\n    'TAA' => '_',    # Stop\r\n    'TAG' => '_',    # Stop\r\n    'TGC' => 'C',    # Cysteine\r\n    'TGT' => 'C',    # Cysteine\r\n    'TGA' => '_',    # Stop\r\n    'TGG' => 'W',    # Tryptophan\r\n    'CTA' => 'L',    # Leucine\r\n    'CTC' => 'L',    # Leucine\r\n    'CTG' => 'L',    # Leucine\r\n    'CTT' => 'L',    # Leucine\r\n    'CCA' => 'P',    # Proline\r\n    'CCC' => 'P',    # Proline\r\n    'CCG' => 'P',    # Proline\r\n    'CCT' => 'P',    # Proline\r\n    'CAC' => 'H',    # Histidine\r\n    'CAT' => 'H',    # Histidine\r\n    'CAA' => 'Q',    # Glutamine\r\n    'CAG' => 'Q',    # Glutamine\r\n    'CGA' => 'R',    # Arginine\r\n    'CGC' => 'R',    # Arginine\r\n    'CGG' => 'R',    # Arginine\r\n    'CGT' => 'R',    # Arginine\r\n    'ATA' => 'I',    # Isoleucine\r\n    'ATC' => 'I',    # Isoleucine\r\n    'ATT' => 'I',    # Isoleucine\r\n    'ATG' => 'M',    # Methionine\r\n    'ACA' => 'T',    # Threonine\r\n    'ACC' => 'T',    # Threonine\r\n    'ACG' => 'T',    # Threonine\r\n    'ACT' => 'T',    # Threonine\r\n    'AAC' => 'N',    # Asparagine\r\n    'AAT' => 'N',    # Asparagine\r\n    'AAA' => 'K',    # Lysine\r\n    'AAG' => 'K',    # Lysine\r\n    'AGC' => 'S',    # Serine\r\n    'AGT' => 'S',    # Serine\r\n    'AGA' => 'R',    # Arginine\r\n    'AGG' => 'R',    # Arginine\r\n    'GTA' => 'V',    # Valine\r\n    'GTC' => 'V',    # Valine\r\n    'GTG' => 'V',    # Valine\r\n    'GTT' => 'V',    # Valine\r\n    'GCA' => 'A',    # Alanine\r\n    'GCC' => 'A',    # Alanine\r\n    'GCG' => 'A',    # Alanine\r\n    'GCT' => 'A',    # Alanine\r\n    'GAC' => 'D',    # Aspartic Acid\r\n    'GAT' => 'D',    # Aspartic Acid\r\n    'GAA' => 'E',    # Glutamic Acid\r\n    'GAG' => 'E',    # Glutamic Acid\r\n    'GGA' => 'G',    # Glycine\r\n    'GGC' => 'G',    # Glycine\r\n    'GGG' => 'G',    # Glycine\r\n    'GGT' => 'G'    # Glycine   \r\n};\r\n\r\ndna = gets.chomp\r\n\r\nwhile exon = gets do\r\n\tdna.gsub!(exon.chomp, '')\r\nend\r\n\r\nputs dna.gsub(\/\\w{3}\/).each(&dict.method(:[]))[0..-1].gsub(\/_.*\/, '')\r\n<\/pre>\n
\u5916\u663e\u5b50\uff08Exon\uff09<\/a>\u3001\u5185\u542b\u5b50\uff08Intron\uff09<\/a><\/p>\n
\r\ns = gets.chomp; n = s.length\r\n\r\ndef cp(a, b)\r\n\treturn a == 'G' && b == 'C' || a == 'C' && b == 'G' || a == 'A' && b == 'T' || a == 'T' && b == 'A'\r\nend\r\n\r\ndef test(s)\t\r\n\tn = s.length\r\n\t0.upto(n\/2){|i|\r\n\t\treturn false if !cp(s[i], s[n-1-i])\r\n\t}\r\n\treturn true\r\nend\r\n\r\n4.upto(8){|len|\t\r\n\tnext if len.odd?\t\r\n\t0.upto(n-len){|l|\r\n\t\tr = l + len - 1\r\n\t\tprint l+1, ' ', len, "\\n" if (test(s[l..r]))\r\n\t}\r\n}\r\n<\/pre>\n
\u6982\u7387<\/h3>\n
\r\nI =->{gets.split.map &:to_f}\r\nI[].each{|ai|\t\r\n\tp (ai**2 + (1-ai)**2) \/ 2\r\n}\r\n<\/pre>\n
\r\nI =->{gets.split.map &:to_f}\r\nm, n = I[]\r\n\r\nI[].each{|ai|  \t\r\n    p (n - m + 1) * ((ai**2 + (1-ai)**2) \/ 2) ** m\r\n}\r\n<\/pre>\n
\u5b57\u7b26\u4e32\u5339\u914d<\/h3>\n
\r\nT = gets().chomp\r\nP = gets().chomp\r\n\r\nTn, Pn = T.length, P.length\r\n\r\nPi = []; Pi[0] = j = -1\r\n\r\n0.upto(Pn-1){|i|\r\n\tj = Pi[j] while (j >= 0 && P[i] != P[j])\r\n\ti += 1; j += 1; Pi[i] = P[i] == P[j] ? Pi[j] : j\t\r\n}\r\n\r\nj = 0\r\n\r\n0.upto(Tn-1){|i|\r\n\tj = Pi[j] while (j >= 0 && T[i] != P[j])\r\n\ti += 1; j += 1; p i-Pn+1 if j == Pn\r\n}\r\n<\/pre>\n
\r\nP = gets().chomp + '$'\r\nPn = P.length\r\n\r\n\r\nPi = []; Pi[0], Pi[1], i, j = -1, 0, 2, 0\r\n\r\nwhile (i < Pn) do\r\n\tif (P[i-1] == P[j]) then\r\n\t\tj +=1; Pi[i] = j; i += 1\r\n\telse\r\n\t\tif (j > 0) then \r\n\t\t\tj = Pi[j]\r\n\t\telse \r\n\t\t\tPi[i] = 0; i += 1\r\n\t\tend\r\n\tend\r\nend\r\n\r\nputs Pi[1..-1]*' '\r\n<\/pre>\n
\r\ns = gets.chomp\r\nt = gets.chomp\r\n\r\ni = 0; t.each_char{|ti|\r\n\ti += 1 while s[i] != ti; i += 1;\r\n\tp i\r\n}\r\n<\/pre>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 1009;\r\n\r\nstring S[N]; int dp[N][N];\r\nint n;\r\n\r\nvoid check(string s){\r\n    FOR(i, 1, n) if (S[i].find(s) == string::npos) return;\r\n    OT(s), exit(0);\r\n}\r\n\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    string s; while (cin >> s){\r\n        S[n++] = s;\r\n    }\r\n\r\n    FOR(i, 1, n) if (SZ(S[i]) < SZ(S[0])) swap(S[0], S[i]);\r\n\r\n    int n0 = SZ(S[0]); DWN(len, n0-1, 0){\r\n        REP(i, n0-len){\r\n            s = S[0].substr(i, len);\r\n            check(s);\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
\u751f\u6210\u6392\u5217\u3001\u7ec4\u5408<\/h3>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 10;\r\nint A[N];\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;\r\n\r\n    printf("%d\\n", f); DO(f){\r\n        REP_1(i, n) OT(A[i]);\r\n        next_permutation(A + 1, A + n + 1);\r\n        puts("");\r\n    }\r\n}\r\n<\/pre>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 10;\r\nint A[N];\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;\r\n    printf("%d\\n", f*_1(n)); DO(f){\r\n        REP(s, _1(n)){\r\n            REP_1(j, n){\r\n                if (!_1(s, (n-j))) putchar('-');\r\n                OT(A[j]);\r\n            }\r\n            puts("");\r\n        }\r\n        next_permutation(A + 1, A + n + 1);\r\n    }\r\n}\r\n<\/pre>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 10;\r\nchar S[N]; int A[N];\r\nint n; LL k;\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    char str[100]; gets(str);\r\n    REP_C(i, strlen(str)) if (str[i] != ' ') S[n++] = str[i];\r\n    RD(k); DO(pow(n, k)){\r\n        DWN(i, k, 0) putchar(S[A[i]]); puts("");\r\n        A[0]++; for (int i=0;A[i]==n;A[i]=0,++A[++i]);\r\n    }\r\n}\r\n<\/pre>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 15;\r\n\r\nchar C[N]; int A[N];\r\nint n, k;\r\n\r\nvoid dfs(int dep = 0){\r\n    if (dep){\r\n        REP(i, dep) putchar(i[A][C]);\r\n        puts("");\r\n    }\r\n\r\n    if (dep == k) return;\r\n    REP(i, n) A[dep]=i, dfs(dep+1);\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    char str[109]; REP_C(i, strlen(gets(str))) if (str[i] != ' ')\r\n        C[n++] = str[i];\r\n    RD(k);\r\n\r\n    dfs();\r\n}\r\n<\/pre>\n
\u641c\u7d22<\/h3>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};\r\nconst int N = 10, L = 3628800;\r\nint n = 10;\r\n\r\nint D[L]; int a[N], st, ed; bool c[N];\r\n\r\nint encode(){ \/\/ Cantor\r\n    int x = 0; REP(i, n){\r\n        int t = 0; FOR(j, i+1, n)\r\n            if (a[i]>a[j]) ++t;\r\n        x = x * (n-i) + t;\r\n    }\r\n    return x;\r\n}\r\n\r\nvoid decode(int x){\r\n    RST(a, c); REP(i, n){\r\n        while (i[a][c]) ++a[i];\r\n        while (x >= F[n-i-1]){\r\n            x -= F[n-i-1]; ++a[i];\r\n            while (i[a][c]) ++a[i];\r\n        }\r\n        i[a][c] = true;\r\n    }\r\n}\r\n\r\nvoid rev(int l, int r){\r\n    REP(i, (r - l + 1) \/ 2)\r\n        swap(a[l+i], a[r-i]);\r\n}\r\n\r\nint Q[L], cz, op; int bfs(){\r\n    if (st == ed) return 0;\r\n    Q[cz = 0] = st, op = 1;\r\n    RST(D); D[st] = 1;\r\n    while (cz < op){\r\n        int u = Q[cz++]; decode(u);\r\n        FOR(len, 1, n){\r\n            REP(l, n - len){\r\n                int r = l + len; rev(l, r); int v = encode(); rev(l, r);\r\n                if (D[v]) continue;\r\n                if (v == ed) return D[u];\r\n                Q[op++] = v;\r\n                D[v] = D[u] + 1;\r\n            }\r\n        }\r\n    }\r\n    return -1;\r\n}\r\n\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    while (~scanf("%d", &a[0])){\r\n        FOR(i, 1, n) --RD(a[i]); st = encode();\r\n        REP(i, n) --RD(a[i]); ed = encode();\r\n        OT(bfs());\r\n    }\r\n}\r\n<\/pre>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\ntemplate<class T1, class T2> ostream& operator <<(ostream& cout, const pair<T1, T2> &rhs){\r\n    cout << rhs.fi+1 << " " << rhs.se+1;\r\n    return cout;\r\n}\r\n\r\nconst int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};\r\nconst int N = 10, L = 3628800;\r\nint n = 10;\r\n\r\nint D[L], pre[L]; PII opt[L]; int a[N], st, ed; bool c[N];\r\n\r\nint encode(){ \/\/ Cantor\r\n    int x = 0; REP(i, n){\r\n        int t = 0; FOR(j, i+1, n)\r\n            if (a[i]>a[j]) ++t;\r\n        x = x * (n-i) + t;\r\n    }\r\n    return x;\r\n}\r\n\r\nvoid decode(int x){\r\n    RST(a, c); REP(i, n){\r\n        while (i[a][c]) ++a[i];\r\n        while (x >= F[n-i-1]){\r\n            x -= F[n-i-1]; ++a[i];\r\n            while (i[a][c]) ++a[i];\r\n        }\r\n        i[a][c] = true;\r\n    }\r\n}\r\n\r\nvoid rev(int l, int r){\r\n    REP(i, (r - l + 1) \/ 2)\r\n        swap(a[l+i], a[r-i]);\r\n}\r\n\r\nvoid print_path(int v){\r\n    if (v == st) return;\r\n    print_path(pre[v]);\r\n    cout << opt[v] << endl;\r\n}\r\n\r\nint Q[L], cz, op; void bfs(){\r\n    if (st == ed) {puts(0); return;}\r\n    Q[cz = 0] = st, op = 1;\r\n    RST(D); D[st] = 1;\r\n    while (cz < op){\r\n        int u = Q[cz++]; decode(u);\r\n        FOR(len, 1, n){\r\n            REP(l, n - len){\r\n                int r = l + len; rev(l, r); int v = encode(); rev(l, r);\r\n                if (D[v]) continue; opt[v] = MP(l, r), pre[v] = u;\r\n                if (v == ed){OT(D[u]), print_path(v); return;}\r\n                Q[op++] = v, D[v] = D[u] + 1;\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    while (~scanf("%d", &a[0])){\r\n        FOR(i, 1, n) --RD(a[i]); st = encode();\r\n        REP(i, n) --RD(a[i]); ed = encode();\r\n        bfs();\r\n    }\r\n}\r\n<\/pre>\n
\u52a8\u6001\u89c4\u5212<\/h3>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 1009;\r\n\r\nchar A[N], B[N];\r\nint dp[N][N], n, m;\r\n\r\nvoid print_path(int i, int j){\r\n    if (!i || !j) return;\r\n    if (A[i] == B[j] && dp[i][j] == dp[i-1][j-1] + 1){\r\n        print_path(i-1, j-1), putchar(A[i]);\r\n    }\r\n    else if (dp[i-1][j] > dp[i][j-1]){\r\n        print_path(i-1, j);\r\n    }\r\n    else{\r\n        print_path(i, j-1);\r\n    }\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    RS(A+1), RS(B+1), n = strlen(A+1), m = strlen(B+1);\r\n\r\n    REP_2_1(i, j, n, m){\r\n        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);\r\n        if (A[i] == B[j]) checkMax(dp[i][j], dp[i-1][j-1] + 1);\r\n    }\r\n\r\n    print_path(n, m);\r\n}\r\n<\/pre>\n
\r\ns = gets.chomp; n = s.length; s = '$' + s\r\nt = gets.chomp; m = t.length; t = '$' + t\r\n\r\ndp = Array.new(n+1){Array.new(m+1){0}}\r\n\r\ndef min(a, b)\r\n\treturn a < b ? a : b\r\nend\r\n\r\n1.upto(n){|i|\r\n\tdp[0][i] = dp[i][0] = i\r\n}\r\n\r\n1.upto(n){|i|\r\n\t1.upto(m){|j|\t\t\r\n\t\tdp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))\r\n\t}\r\n}\r\n\r\np dp[n][m]\r\n<\/pre>\n
\r\ns = gets.chomp; n = s.length; s = '$' + s\r\nt = gets.chomp; m = t.length; t = '$' + t\r\n\r\ndp = Array.new(n+1){Array.new(m+1){0}}\r\n\r\ndef min(a, b)\r\n\treturn a < b ? a : b\r\nend\r\n\r\n1.upto(n){|i|\r\n\tdp[0][i] = dp[i][0] = i\r\n}\r\n\r\n1.upto(n){|i|\r\n\t1.upto(m){|j|\t\t\r\n\t\tdp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))\r\n\t}\r\n}\r\n\r\n# build alignment .. .\r\ns_ = t_ = ''; i, j = n, m\r\nwhile !i.zero? || !j.zero? do\t\r\n\tif (j.zero? || dp[i][j] == dp[i-1][j] + 1) then\r\n\t\ts_ += s[i]; t_ += '-'\r\n\t\ti -= 1\r\n\telsif (i.zero? || dp[i][j] == dp[i][j-1] + 1) then\r\n\t\ts_ += '-'; t_ += t[j]\r\n\t\tj -= 1\r\n\telse\t\t\r\n\t\ts_ += s[i]; t_ += t[j]\t\t\r\n\t\ti -= 1; j -= 1\r\n\tend\r\nend\r\n\r\ns_.reverse!; t_.reverse!\r\nputs dp[n][m], s_, t_\r\n<\/pre>\n
\r\n<\/pre>\n
\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/rosalind.info\/problems\/as-graph\/ http:\/\/en.wikipedia.org\/wiki\/Bioinformatics<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-569","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-9b","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/569","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=569"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/569\/revisions"}],"predecessor-version":[{"id":570,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/569\/revisions\/570"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=569"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=569"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=569"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}