diff options
Diffstat (limited to 'string')
| -rw-r--r-- | string/kmp.cpp | 8 | ||||
| -rw-r--r-- | string/longestCommonSubsequence.cpp | 8 | ||||
| -rw-r--r-- | string/suffixAutomaton.cpp | 9 | ||||
| -rw-r--r-- | string/suffixTree.cpp | 3 | ||||
| -rw-r--r-- | string/trie.cpp | 2 |
5 files changed, 14 insertions, 16 deletions
diff --git a/string/kmp.cpp b/string/kmp.cpp index 282019e..12ae3eb 100644 --- a/string/kmp.cpp +++ b/string/kmp.cpp @@ -1,8 +1,8 @@ vector<int> kmpPreprocessing(const string& sub) { - vector<int> b(sub.size() + 1); + vector<int> b(sz(sub) + 1); b[0] = -1; int i = 0, j = -1; - while (i < (int)sub.size()) { + while (i < sz(sub)) { while (j >= 0 && sub[i] != sub[j]) j = b[j]; i++; j++; b[i] = j; @@ -12,10 +12,10 @@ vector<int> kmpPreprocessing(const string& sub) { vector<int> kmpSearch(const string& s, const string& sub) { vector<int> pre = kmpPreprocessing(sub), result; int i = 0, j = 0; - while (i < (int)s.size()) { + while (i < sz(s)) { while (j >= 0 && s[i] != sub[j]) j = pre[j]; i++; j++; - if (j == (int)sub.size()) { + if (j == sz(sub)) { result.push_back(i - j); j = pre[j]; }} diff --git a/string/longestCommonSubsequence.cpp b/string/longestCommonSubsequence.cpp index dd2368e..fa1adb6 100644 --- a/string/longestCommonSubsequence.cpp +++ b/string/longestCommonSubsequence.cpp @@ -1,12 +1,12 @@ string lcss(string& a, string& b) { - vector<vector<int>> m(a.size() + 1, vector<int>(b.size() + 1)); - for(int y = a.size() - 1; y >= 0; y--) { - for(int x = b.size() - 1; x >= 0; x--) { + vector<vector<int>> m(sz(a) + 1, vector<int>(sz(b) + 1)); + for(int y = sz(a) - 1; y >= 0; y--) { + for(int x = sz(b) - 1; x >= 0; x--) { if(a[y] == b[x]) m[y][x] = 1 + m[y+1][x+1]; else m[y][x] = max(m[y+1][x], m[y][x+1]); }} // Für die Länge: return m[0][0]; string res; int x=0; int y=0; - while(x < b.size() && y < a.size()) { + while(x < sz(b) && y < sz(a)) { if(a[y] == b[x]) res += a[y++], x++; else if(m[y][x+1] > m[y+1][x+1]) x++; else y++; diff --git a/string/suffixAutomaton.cpp b/string/suffixAutomaton.cpp index 15265c8..69aa979 100644 --- a/string/suffixAutomaton.cpp +++ b/string/suffixAutomaton.cpp @@ -1,5 +1,5 @@ constexpr char MIN_CHAR = 'a'; -constexpr long long ALPHABET_SIZE = 26; +constexpr ll ALPHABET_SIZE = 26; struct SuffixAutomaton { struct State { int length, link; @@ -9,8 +9,7 @@ struct SuffixAutomaton { vector<State> states; int size, last; - SuffixAutomaton(string &s) { - states.resize(2 * sz(s)); + SuffixAutomaton(const string &s) : states(2*sz(s)) { size = 1; last = 0; states[0].length = 0; states[0].link = -1; @@ -46,9 +45,9 @@ struct SuffixAutomaton { // Pair with start index and length of LCS. // Index in parameter t. - pair<int, int> longestCommonSubstring(string &t) { + pair<int, int> longestCommonSubstring(const string &t) { int v = 0, l = 0, best = 0, bestpos = 0; - for (int i = 0; i < (int)t.size(); i++) { + for (int i = 0; i < sz(t); i++) { int c = t[i] - MIN_CHAR; while (v && !states[v].next[c]) { v = states[v].link; diff --git a/string/suffixTree.cpp b/string/suffixTree.cpp index 7af3ee6..2601c34 100644 --- a/string/suffixTree.cpp +++ b/string/suffixTree.cpp @@ -53,7 +53,6 @@ struct SuffixTree { if (!tree[curVert].next.count(s[curEdge])) { int leaf = newVert(pos, sz(s)); tree[curVert].next[s[curEdge]] = leaf; - tree[curVert].next[s[curEdge]] = leaf; addSuffixLink(curVert); } else { int nxt = tree[curVert].next[s[curEdge]]; @@ -77,7 +76,7 @@ struct SuffixTree { curLen--; curEdge = pos - remainder + 1; } else { - curVert = tree[curVert].suffix ? tree[curVert].suffix + curVert = tree[curVert].suffix ? tree[curVert].suffix : root; }}} };
\ No newline at end of file diff --git a/string/trie.cpp b/string/trie.cpp index f112e1e..0544a9f 100644 --- a/string/trie.cpp +++ b/string/trie.cpp @@ -11,7 +11,7 @@ int insert(vector<int>& word) { for (int c : word) { trie[id].words++; if (trie[id].children[c] < 0) { - trie[id].children[c] = trie.size(); + trie[id].children[c] = sz(trie); trie.emplace_back(); } id = trie[id].children[c]; |