LeetCode.472 Concatenated Words

1.Problem
Concatenated Words - LeetCode

2.Idea
Trie + DFS

3.Source

 class TrieNode {  
   public:  
   bool isKey = false;  
   TrieNode* child[26];  
 };  
 class Solution {  
 public:  
   TrieNode* root = new TrieNode();  
   void addWord(string word) {  
     TrieNode* curr = root;  
     for(char c : word) {  
       if(!curr->child[c - 'a'])  
         curr->child[c - 'a'] = new TrieNode();  
       curr = curr->child[c - 'a'];  
     }  
     curr->isKey = true;  
   }  
   bool search(string word, int index, int count) {  
     if(index >= word.size()) return count >= 2;  
     TrieNode* curr = root;  
     for(int i= index; i < word.size(); i++) {  
       char c = word[i];  
       if(!curr->child[c - 'a'])  
         return false;  
       curr = curr->child[c - 'a'];  
       if(curr->isKey) {  
         if(search(word, i+1, count + 1))  
           return true;  
       }  
     }  
     return false;  
   }  
   vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {  
     vector<string> res;  
     if(words.size() == 0) return res;  
     for(string s : words)   
       addWord(s);  
     for(string s : words) {  
       if(search(s, 0, 0))  
         res.push_back(s);  
     }  
     return res;  
   }  
 };  

POJ.3729 Facer’s string

1.Problem
3729 -- Facer’s string (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3.Source Code

 const int MAXN = 50010;  
 int n, N, M, k, K;  
 int Rank[MAXN * 2];  
 int tmp[MAXN * 2];  
 int sa[MAXN * 2];  
 int lcp[MAXN * 2];  
 int s[MAXN * 2];  
 bool compare_sa(const int& i, const int& j) {  
      if (Rank[i] != Rank[j])return Rank[i] < Rank[j];  
      else {  
           int ri = i + k <= n ? Rank[i + k] : -1;  
           int rj = j + k <= n ? Rank[j + k] : -1;  
           return ri < rj;  
      }  
 }  
 void construct_sa(const int *S, int *sa) {  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp(const int *S, int *sa, int *lcp) {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)Rank[sa[i]] = i;  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++) {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)h--;  
           for (; j + h < n&&i + h < n; h++) {  
                if (S[j + h] != S[i + h])break;  
           }  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 long long calc(int K) {  
      int A = 0, B = 0;  
      long long res = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                if (B > 0)res += A;  
                A = 0; B = 0;  
           }  
           if (sa[i + 1] < N)A++;  
           if (sa[i + 1] > N) B++;  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (scanf("%d%d%d\n", &N, &M, &K) != EOF) {  
           for (int i = 0; i < N; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           s[N] = '$';  
           for (int i = N + 1; i < N + M + 1; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           n = N + M + 1;  
           s[n] = 0;  
           construct_sa(s, sa);  
           construct_lcp(s, sa, lcp);  
           printf("%lld\n", calc(K) - calc(K+1));  
      }  
 }  

POJ.3415 Common Substrings

1.Problem
3415 -- Common Substrings (poj.org)

2.Idea
Suffix Array
Monotonic Stack

3.Source

 const int MAX_L = 100000 + 1;  
 const int MAX_N = 2 * MAX_L + 1;  
 std::string S;  
 int n, k;  
 int sa[MAX_N + 1], lcp[MAX_N + 1];   
 int Rank[MAX_N + 1], tmp[MAX_N + 1];  
 bool compare_sa(const int i, const int j)  
 {  
      if (Rank[i] != Rank[j])  
      {  
           return Rank[i] < Rank[j];  
      }  
      return (i + k <= n ? Rank[i + k] : -1) < (j + k <= n ? Rank[j + k] : -1);  
 }  
 void construct_sa()  
 {  
      for (int i = 0; i <= n; i++)  
      {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k <<= 1)  
      {  
           std::sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++)  
           {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++)  
           {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp()  
 {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)  
      {  
           Rank[sa[i]] = i;  
      }  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++)  
      {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)  
           {  
                h--;  
           }  
           for (; i + h < n && j + h < n && S[i + h] == S[j + h]; h++);  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 int Stack[MAX_N][2];  
 long long contribution, top;  
 using namespace std;  
 long long calc(int K, int l1, bool is_s1)  
 {  
      long long ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                top = contribution = 0;  
           }  
           else {  
                int size = 0;  
                if ((is_s1 && sa[i] < l1) || (!is_s1 && sa[i] > l1)) {  
                     ++size;  
                     contribution += lcp[i] - K + 1;  
                }  
                while (top > 0 && lcp[i] <= Stack[top - 1][0]) {  
                     --top;  
                     contribution -= Stack[top][1] * (Stack[top][0] - lcp[i]);  
                     size += Stack[top][1];  
                }  
                if (size) {  
                     Stack[top][0] = lcp[i];  
                     Stack[top][1] = size;  
                     ++top;  
                }  
                if ((is_s1 && sa[i + 1] > l1) || (!is_s1 && sa[i + 1] < l1)) {  
                     ans += contribution;  
                }  
           }  
      }  
      return ans;  
 }  
 void solve()  
 {  
      int k;  
      while (scanf("%d", &k), k) {  
           string s1, s2;  
           cin >> s1 >> s2;  
           int l1 = s1.length();  
           int l2 = s2.length();  
           S = s1 + "$" + s2;  
           n = l1 + l2 + 1;  
           construct_sa();  
           construct_lcp();  
           printf("%lld\n", calc(k, l1, true) + calc(k, l1, false));  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.1509 Glass Beads

1.Problem
1509 -- Glass Beads (poj.org)

2.Idea
Suffix Array

3.Source Code

 const int MAXN = 20010;  
 int Rank[MAXN], tmp[MAXN];  
 int n, k;  
 int sa[MAXN];  
 bool compare_sa(int i, int j) {  
      if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];  
      int ri = (i + k <= n) ? Rank[i + k] : -1;  
      int rj = (j + k <= n) ? Rank[j + k] : -1;  
      return ri < rj;  
 }  
 void createSA(const string& s, int* sa) {  
      n = s.size();  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? s[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) Rank[i] = tmp[i];  
      }  
 }  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S;  
           getInput(S);  
           createSA(S + S + (char)('z' + 1), sa);  
           int ans = -1;  
           for (int i = 0; i <= n; i++) {  
                if (sa[i] < S.length()) {  
                     ans = sa[i] + 1;  
                     break;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2217 Secretary

1.Problem
2217 -- Secretary (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3. Source Code

 const int MAXN = 20010;  
 namespace SA {  
      int rank[MAXN], tmp[MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const string& s, int* sa) {  
           n = s.size();  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
      namespace LCP {  
           int rank[MAXN];  
           void createLCP(const string& s, const int* sa, int* lcp) {  
                int n = s.size();  
                for (int i = 0; i <= n; i++) rank[sa[i]] = i;  
                int h = 0;  
                lcp[0] = 0;  
                for (int i = 0; i < n; i++) {  
                     int j = sa[rank[i] - 1];  
                     h = max(0, h - 1);  
                     for (; j + h < n && i + h < n; h++) {  
                          if (s[j + h] != s[i + h]) break;  
                     }  
                     lcp[rank[i] - 1] = h;  
                }  
           }  
      } // namespace LCP  
 } // namespace SA  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 int sa[MAXN], lcp[MAXN];  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S, T;  
           getInput(S); getInput(T);  
           int n = S.size(), m = T.size();  
           S += '\n';  
           S += T;  
           SA::createSA(S, sa);  
           SA::LCP::createLCP(S, sa, lcp);  
           int nm = S.size(), ans = 0;  
           for (int i = 0; i < nm; i++) {  
                if (sa[i] < n && sa[i + 1] < n) continue;  
                if (sa[i] > n && sa[i + 1] > n) continue;  
                ans = max(ans, lcp[i]);  
           }  
           printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3581 Sequence

1.Problem
http://poj.org/problem?id=3581

2.Idea
Suffix Array

3.Source

 const int MAXN = 20010;  
 namespace SA {  
      int rank[2 * MAXN], tmp[2 * MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const int* s, int N, int* sa) {  
           n = N;  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
 }  
 int N, A[MAXN], rev[2 * MAXN], sa[2 * MAXN];  
 void solve()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d", A + i);  
      reverse_copy(A, A + N, rev);  
      SA::createSA(rev, N, sa);  
      int p1, p2;  
      for (int i = 0; i <= N; i++) {  
           p1 = N - sa[i];  
           if (p1 > 0 && N - p1 >= 2) break;  
      }  
      int m = N - p1;  
      reverse_copy(A + p1, A + N, rev);  
      reverse_copy(A + p1, A + N, rev + m);  
      SA::createSA(rev, 2 * m, sa);  
      for (int i = 0; i <= 2 * m; i++) {  
           p2 = m - sa[i];  
           if (p2 > 0 && m - p2 >= 1) break;  
      }  
      for (int i = p1 - 1; i >= 0; i--) printf("%d\n", A[i]);  
      for (int i = p1 + p2 - 1; i >= p1; i--) printf("%d\n", A[i]);  
      for (int i = N - 1; i >= p1 + p2; i--) printf("%d\n", A[i]);  
 }  
 int main() {  
      //ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3690 Constellations

1.Problem
http://poj.org/problem?id=3690

2.Idea
Rolling Hash D2

3.Source Code

 typedef unsigned long long ull;  
 int N, M, T, P, Q;  
 char field[1100][1100];  
 char patterns[110][1100][1100];  
 ull Hash[1100][1100], tmp[1100][1100];  
 void compute_hash(char a[1100][1100], int n, int m)  
 {  
      const ull B1 = 9973;  
      const ull B2 = 1000000007;  
      ull t1 = 1;  
      for (int j = 0; j < Q; j++) t1 *= B1;  
      for (int i = 0; i < n; i++) {  
           ull e = 0;  
           for (int j = 0; j < Q; j++) {  
                e = e * B1 + a[i][j];  
           }  
           for (int j = 0; j + Q <= m; j++) {  
                tmp[i][j] = e;  
                if (j + Q < m) e = e * B1 - t1 * a[i][j] + a[i][j + Q];  
           }  
      }  
      ull t2 = 1;  
      for (int i = 0; i < P; i++) t2 *= B2;  
      for (int j = 0; j + Q <= m; j++) {  
           ull e = 0;  
           for (int i = 0; i < P; i++) {  
                e = e * B2 + tmp[i][j];  
           }  
           for (int i = 0; i + P <= n; i++) {  
                Hash[i][j] = e;  
                if (i + P < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + P][j];  
           }  
      }  
 }  
 void solve()  
 {  
      int cnt = 0;  
      while (true) {  
           scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q);  
           if (N + M + T + P + Q == 0) break;  
           cnt++;  
           for (int i = 0; i < N; ++i) {  
                scanf("%s", field[i]);  
           }  
           for (int t = 0; t < T; ++t) {  
                for (int i = 0; i < P; ++i) {  
                     scanf("%s", patterns[t][i]);  
                }  
           }  
           multiset<ull> unseen;  
           for (int k = 0; k < T; k++) {  
                compute_hash(patterns[k], P, Q);  
                unseen.insert(Hash[0][0]);  
           }  
           compute_hash(field, N, M);  
           for (int i = 0; i + P <= N; i++) {  
                for (int j = 0; j + Q <= M; j++) {  
                     unseen.erase(Hash[i][j]);  
                }  
           }  
           printf("Case %d: %d\n", cnt, T - unseen.size());  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ. 3691 DNA repair

1.Problem
http://poj.org/problem?id=3691

2.Idea
Here

3.Source

 const int MAXK = 1000;  
 const int MAXLEN = 1010;  
 const string AGCT = "AGCT";  
 int nextState[MAXK][4];  
 bool ng[MAXK];  
 int dp[MAXLEN][MAXK];  
 int solve(const vector<string>& ngWords, const string& init) {  
      vector<string> pfx;  
      int n = ngWords.size();  
      // 状態の列挙  
      for (int i = 0; i < n; i++) {  
           string s = ngWords[i];  
           for (int j = 0; j <= (int)s.size(); j++) {  
                pfx.push_back(s.substr(0, j));  
           }  
      }  
      sort(pfx.begin(), pfx.end());  
      pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());  
      int K = pfx.size();  
      // 状態の遷移  
      for (int i = 0; i < K; i++) {  
           for (int j = 0; j < 4; j++) {  
                string s = pfx[i] + AGCT.substr(j, 1);  
                while (1) {  
                     int nk = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin();  
                     if (nk < K && pfx[nk] == s) {  
                          nextState[i][j] = nk;  
                          break;  
                     }  
                     s = s.substr(1);  
                }  
           }  
      }  
      // 状態がngかどうか  
      for (int i = 0; i < K; i++) {  
           ng[i] = false;  
           int sl = pfx[i].size();  
           for (int j = 0; j < n; j++) {  
                int wl = ngWords[j].size();  
                if (sl < wl) continue;  
                if (pfx[i].substr(sl - wl) == ngWords[j]) {  
                     ng[i] = true;  
                     break;  
                }  
           }  
      }  
      // dp  
      int length = init.size();  
      for (int i = 0; i <= length; i++) for (int k = 0; k < K; k++) {  
           dp[i][k] = INF;  
      }  
      dp[0][0] = 0;  
      for (int l = 0; l < length; l++) for (int k = 0; k < K; k++) {  
           if (dp[l][k] == INF) continue;  
           if (ng[k]) continue;  
           for (int j = 0; j < 4; j++) {  
                int plus = (init[l] == AGCT[j]) ? 0 : 1;  
                int ns = nextState[k][j];  
                if (ng[ns]) continue;  
                dp[l + 1][ns] = min(dp[l][k] + plus, dp[l + 1][ns]);  
           }  
      }  
      int ans = INF;  
      for (int k = 0; k < K; k++) {  
           if (ng[k]) continue;  
           ans = min(ans, dp[length][k]);  
      }  
      if (ans == INF) ans = -1;  
      return ans;  
 }  
 int main() {  
      cin.tie(0);  
      ios::sync_with_stdio(false);  
      int T = 0;  
      int n;  
      while (cin >> n) {  
           if (n == 0) break;  
           T++;  
           vector<string> ngWords;  
           for (int i = 0; i < n; i++) {  
                string s;  
                cin >> s;  
                ngWords.push_back(s);  
           }  
           string init;  
           cin >> init;  
           printf("Case %d: %d\n", T, solve(ngWords, init));  
      }  
      return 0;  
 }  

POJ.1598 Excuses, Excuses!

1.Problem
http://poj.org/problem?id=1598

2.Idea
KMP string matching

3.Source

 int nextarray[1000006];  
 void getnext(string s)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < s.size())  
      {  
           if (j == -1 || s[j] == s[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 int kmp(string &a, string &b)  
 {  
      int i = 0, j = 0, ans = 0;  
      while (i < a.size())  
      {  
           if (j == -1 || a[i] == b[j])  
                ++i, ++j;  
           else  
                j = nextarray[j];  
           if (j == b.size())  
                ++ans, j = nextarray[j];  
      }  
      return ans;  
 }  
 int k, e;  
 string kw[100], es[100];  
 int score[100];  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d%d\n", &k, &e) != EOF) {  
           for (int i = 0; i < k; i++) {  
                cin >> kw[i];  
           }  
           for (int i = 0; i < e; i++) {  
                getline(cin, es[i]);  
                transform(es[i].begin(), es[i].end(), es[i].begin(), ::tolower);  
           }  
           memset(score, 0, sizeof score);  
           int mx = -1;  
           for (int i = 0; i < e; i++) {  
                for (int j = 0; j < k; j++) {  
                     getnext(kw[j]);  
                     score[i] += kmp(es[i], kw[j]);  
                }  
                mx = max(mx, score[i]);  
           }  
           cout << "Excuse Set #" << t++ << endl;  
           for (int i = 0; i < e; i++) {  
                if (score[i] == mx) {  
                     cout << es[i] << endl;  
                }  
           }  
           cout << endl;  
      }  
      return 0;  
 }  

POJ.2406 Power Strings

1.Problem
http://poj.org/problem?id=2406

2.Idea
KMP pre-processing

3.Source

 char s[1000006];  
 int n;  
 int nextarray[1000006];  
 void getnext()  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < n)  
      {  
           if (j == -1 || s[j] == s[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 int main()  
 {  
      while (scanf("%s", &s) > 0) {  
           n = strlen(s);  
           if (s[0] == '.' && n == 1) break;  
           getnext();  
           if (n % (n - nextarray[n]) == 0)  
                cout << n / (n - nextarray[n]) << endl;  
           else  
                cout << 1 << endl;  
      }  
      return 0;  
 }  

POJ.2752 Seek the Name, Seek the Fame

1.Problem
http://poj.org/problem?id=2752

2.Idea
calculate all prefix&suffix by KMP.

3.Source

 string s;  
 int nextarray[400005];  
 void getnext(string &str)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < str.size())  
      {  
           if (j == -1 || str[j] == str[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 void solve()  
 {  
      getnext(s);  
      int cur = s.size();  
      vector<int> ans;  
      while (cur > 0) {  
           ans.push_back(cur);  
           cur = nextarray[cur];  
      }  
      sort(ans.begin(), ans.end());  
      for (int i = 0; i < ans.size(); i++) {  
           cout << ans[i] << " ";  
      }  
      cout << endl;  
 }  
 int main()  
 {  
      while (cin >> s) {  
           solve();  
      }  
      return 0;  
 }  

POJ.1080 Human Gene Functions

1.Problem
http://poj.org/problem?id=1080

2.Idea
DP + string

3.Source

 int mat[5][5] = {  
      5, -1, -2, -1, -3,  
      -1, 5, -3, -2, -4,  
      -2, -3, 5, -2, -2,  
      -1, -2, -2, 5, -1,  
      -3, -4, -2, -1, 0,  
 };  
 int dp[102][102];  
 int main()  
 {  
      int t;  
      cin >> t;  
      map<char, int> dic;  
      dic['A'] = 0; dic['C'] = 1; dic['G'] = 2;  
      dic['T'] = 3; dic['-'] = 4;  
      while (t--) {  
           int l, m;  
           string s, t;  
           cin >> l >> s;  
           cin >> m >> t;  
           memset(dp, 0, sizeof dp);  
           for (int i = 0; i < l; i++) dp[i + 1][0] = dp[i][0] + mat[dic[s[i]]][dic['-']];  
           for (int j = 0; j < m; j++) dp[0][j + 1] = dp[0][j] + mat[dic['-']][dic[t[j]]];  
           for (int i = 0; i < l; i++) {  
                for (int j = 0; j < m; j++) {  
                     dp[i + 1][j + 1] = max(dp[i + 1][j] + mat[dic['-']][dic[t[j]]],  
                                           max(dp[i][j + 1] + mat[dic[s[i]]][dic['-']],  
                                       dp[i][j] + mat[dic[s[i]]][dic[t[j]]]));                           
                }  
           }  
           cout << dp[l][m] << endl;  
      }  
      return 0;  
 }  

POJ.2121 Inglish-Number Translator

1.Problem
http://poj.org/problem?id=2121

2.Idea
Calculate digits for three parts of million, thousand, unit.

3.Source

 string words[] =  
 { "zero", "one", "two", "three",  
 "four", "five", "six", "seven",  
 "eight","nine", "ten", "eleven", "twelve",  
 "thirteen", "fourteen", "fifteen", "sixteen",  
 "seventeen", "eighteen", "nineteen", "twenty",  
 "thirty", "forty", "fifty", "sixty", "seventy",  
 "eighty", "ninety","hundred", "thousand", "million" };  
 int num2str[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,30,40,50,60,70,80,90,100,1000,1000000 };  
 int main()  
 {  
      map<string, int> mp;  
      for (int i = 0; i < 31; i++) {  
           mp[words[i]] = num2str[i];  
      }  
      string str, line;  
      while (getline(cin, line)) {  
           if (line.length() == 0) break;  
           istringstream input(line);  
           bool neg = 0;  
           ll ans = 0, pre = 0;  
           while (input >> str) {  
                if (str == "negative") neg = 1;  
                else if (str == "hundred") pre *= 100;  
                else if (str == "thousand") {  
                     pre *= 1000;  
                     ans += pre;  
                     pre = 0;  
                }  
                else if (str == "million") {  
                     pre *= 1000000;  
                     ans += pre;  
                     pre = 0;  
                }  
                else {  
                     pre += mp[str];  
                }  
           }  
           ans += pre;  
           if (neg) ans *= -1;  
           cout << ans << endl;  
      }  
      return 0;  
 }  

POJ. 2192 Zipper

1.Problem
http://poj.org/problem?id=2192

2.Idea
dp[i][j]: true if suffix i+j of C can be made from suffix i of A + suffix j of B, otherwize false.

3.Source

 int t, n, m;  
 string a, b, c;  
 bool dp[202][202];  
 int main()  
 {  
      cin >> t;  
      for (int T = 1; T <= t; T++) {  
           cin >> a >> b >> c;  
           n = a.size();  
           m = b.size();  
           memset(dp, 0, sizeof dp);  
           dp[0][0] = true;  
           for (int i = 0; i <= n; i++) {  
                for (int j = 0; j <= m; j++) {  
                     if (i - 1 >= 0 && a[i - 1] == c[i + j - 1] && dp[i - 1][j]) dp[i][j] = true;  
                     if (j - 1 >= 0 && b[j - 1] == c[i + j - 1] && dp[i][j - 1]) dp[i][j] = true;  
                }  
           }  
           if (dp[n][m]) cout << "Data set " << T << ": yes" << endl;  
           else cout << "Data set " << T << ": no" << endl;  
      }  
      return 0;  
 }  

LeetCode.1419 Minimum Number of Frogs Croaking

1.Problem
https://leetcode.com/problems/minimum-number-of-frogs-croaking/

2.Idea
Counting chars while making sure order and number are correct.

3.Souce

 bool cmp(string a, string b)  
 {  
      return std::stoi(a) < std::stoi(b);  
 }  
 class Solution {  
 public:  
      vector<vector<string>> displayTable(vector<vector<string>>& orders) {  
           int N = orders.size();  
           map< pair<string, string>, int> ords;  
           vector<string> tables, items;  
           for (int i = 0; i < N; i++) {  
                string table = orders[i][1];  
                string item = orders[i][2];  
                ords[make_pair(table, item)]++;  
                tables.push_back(table);  
                items.push_back(item);  
           }  
           sort(tables.begin(), tables.end(), cmp);  
           std::vector<string>::iterator it;  
           it = std::unique(tables.begin(), tables.end());   
           tables.resize(std::distance(tables.begin(), it));  
           sort(items.begin(), items.end());  
           it = std::unique(items.begin(), items.end());  
           items.resize(std::distance(items.begin(), it));  
           int n = tables.size() + 1, m = items.size() + 1;  
           vector<vector<string>> ans(1);  
           ans[0].push_back("Table");  
           for (int i = 0; i < items.size(); i++) {  
                ans[0].push_back(items[i]);  
           }  
           for (int i = 0; i < tables.size(); i++) {  
                vector<string> tmp(m);  
                tmp[0] = tables[i];  
                ans.push_back(tmp);  
           }  
           for (int i = 1; i < n; i++) {  
                for (int j = 1; j < m; j++) {  
                     if (ords.find(make_pair(ans[i][0], ans[0][j])) == ords.end()) {  
                          ans[i][j] = "0";  
                     }  
                     else {  
                          ans[i][j] = std::to_string(ords[make_pair(ans[i][0], ans[0][j])]);  
                     }  
                }  
           }  
           return ans;  
      }  
 };  

POJ.3461 Oulipo

1.Problem
http://poj.org/problem?id=3461

2.Idea
KMP method for string matching

3.Source

 const int maxw = 10000 + 10;   
 const int maxt = 1000000 + 10;   
 //KMP Method  
 int match(char w[], char s[], int next[])  
 {   
      int cnt = 0;  
      int slen = strlen(s);  
      int wlen = strlen(w);  
      int p = 0, cur = 0;  
      while (cur < slen) {   
           if (s[cur] == w[p]) {   
                ++cur;  
                ++p;  
           }  
           else if (p >= 0) {   
                p = next[p];  
           }  
           else {  
                ++cur;  
                p = 0;  
           }  
           if (p == wlen) {   
                ++cnt;  
                p = next[p];  
           }  
      }  
      return cnt;  
 }  
 int main(void)  
 {  
      int loop;  
      scanf("%d", &loop);  
      while (loop--) {  
           char w[maxw], t[maxt];  
           scanf("%s%s", w, t);   
           int suffix[maxw]; // prefix function for word w  
           suffix[0] = -1;  
           suffix[1] = 0;  
           int p = 0;  
           for (int cur = 2; cur <= strlen(w); cur++) {  
                while (p >= 0 && w[p] != w[cur - 1])  
                     p = suffix[p];  
                suffix[cur] = ++p;  
           }  
           printf("%d\n", match(w, t, suffix));   
      }  
      return 0;  
 }  

LeetCode.678 Valid Parenthesis String

1.Problem
https://leetcode.com/problems/valid-parenthesis-string/

2.Idea
Greedy approach. Evaluating possible lower and upper bound value of open parenthesis number.

3.Source

 class Solution {  
 public:  
   bool checkValidString(string s) {  
     int lo = 0, hi = 0;  
     for (int i = 0; i < s.size(); i++) {  
       lo += s[i] == '(' ? 1 : -1;  
       hi += s[i] != ')' ? 1 : -1;  
       if (hi < 0) break;  
       lo = std::max(lo, 0);  
     }  
     return lo == 0;  
   }  
 };  

POJ.3080 Blue Jeans

1.Problem
http://poj.org/problem?id=3080

2.Idea
Brute Force + KMP

3.Source

 int nextarray[65];  
 string str[15];  
 void getnext(string &str)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < str.size())  
      {  
           if (j == -1 || str[j] == str[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 bool kmp(string &a, string &b)  
 {  
      int i = 0, j = 0, ans = 0;  
      while (i < a.size())  
      {  
           if (j == -1 || a[i] == b[j])  
                ++i, ++j;  
           else  
                j = nextarray[j];  
           if (j == b.size())  
                ++ans, j = nextarray[j];  
      }  
      if (ans)  
           return true;  
      return false;  
 }  
 int main()  
 {  
      string s;  
      ios::sync_with_stdio(0);  
      int n;  
      cin >> n;  
      for (int i = 0; i < n; ++i)  
      {  
           int m;  
           cin >> m;  
           for (int j = 0; j < m; ++j)  
                cin >> str[j];  
           string ans = "";  
           for (int j = 0; j < str[0].size(); ++j)  
                for (int k = 1; k + j <= str[0].size(); ++k)  
                {  
                     s = str[0].substr(j, k);  
                     getnext(s);  
                     bool flag = 0;  
                     for (int l = 1; l < m; ++l)  
                          //cout << kmp(str[l], s) << " " << str[l] << " " << s << endl;  
                          if (!kmp(str[l], s))  
                               flag = 1;  
                     //cout << flag << endl;  
                     if (!flag)  
                     {  
                          if (ans.size() < s.size())  
                               ans = s;  
                          else if (ans.size() == s.size() && ans > s)  
                               ans = s;  
                          //cout << ans << endl;  
                     }  
                }  
           if (ans.size() < 3)  
                cout << "no significant commonalities" << endl;  
           else  
                cout << ans << endl;  
      }  
      return 0;  
 }  

CodeForces.1326D2 Prefix-Suffix Palindrome (Hard version)

1.Problem
https://codeforces.com/contest/1326/problem/D2

2.Idea
KMP algorithm

3.Source

 string s;  
 int n;  
 //kmp algorithm: returns len of the longest pre==suf   
 int longest_palindrome_prefix(const string s)  
 {  
      string kmprev = s;  
      reverse(kmprev.begin(), kmprev.end());  
      string kmp = s + "#" + kmprev;  
      vector<int> lps(kmp.size(), 0);  
      for (int i = 1; i < (int)lps.size(); ++i)  
      {  
           int prev_idx = lps[i - 1];  
           while (prev_idx > 0 && kmp[i] != kmp[prev_idx])  
           {  
                prev_idx = lps[prev_idx - 1];  
           }  
           lps[i] = prev_idx + (kmp[i] == kmp[prev_idx] ? 1 : 0);  
      }  
      return lps[lps.size() - 1];  
 }  
 int32_t main()  
 {  
      int t;  
      cin >> t;  
      while(t--)  
      {  
           cin >> s;  
           n = s.length();  
           int ln = 0;  
           for (int i = 0, j = n - 1; i < j; ++i, --j)  
                if (s[i] == s[j])  
                     ln++;  
                else  
                     break;  
           int rem = n - 2 * ln;  
           string ans;  
           if (ln)     ans = s.substr(0, ln);  
           if (rem > 0)  
           {  
                string st = s.substr(ln, rem);  
                int pre = longest_palindrome_prefix(st);  
                reverse(st.begin(), st.end());  
                int suf = longest_palindrome_prefix(st);  
                if (pre > suf) {  
                     reverse(st.begin(), st.end());  
                     ans += st.substr(0, pre);  
                }  
                else {  
                     ans += st.substr(0, suf);  
                }  
           }  
           if (ln) ans += s.substr(n - ln, ln);  
           std::cout << ans << '\n';  
      }  
      return 0;  
 }  

POJ.1795 DNA Laboratory

1.Problem
http://poj.org/problem?id=1795

2.Idea and Source:
https://blog.csdn.net/GYH0730/article/details/90344515