| 54 | } |
| 55 | } row, bs[SIGMA], x; |
| 56 | int main() { |
| 57 | for (int i = 0; i < SIGMA; ++i) bs[i].clear(); |
| 58 | string s, t; |
| 59 | cin >> s >> t; |
| 60 | int n = s.size(), m = t.size(); |
| 61 | for (int i = 0; i < n; ++ i) { |
| 62 | bs[s[i] - 'a'].set(i); |
| 63 | } |
| 64 | M = n / W + (n % W != 0); |
| 65 | row.clear(); |
| 66 | for (int i = 0; i < m; ++i) { |
| 67 | for (int j = 0; j < M; ++j) { |
| 68 | x.u[j] = row.u[j] | bs[t[i] - 'a'].u[j]; |
| 69 | } |
| 70 | row.shl(); |
| 71 | row.sub(x); |
| 72 | row.yo(x); |
| 73 | //printf("%d\n", row.count()); //lcs of prefix of t and whole s |
| 74 | } |
| 75 | cout << row.count() << '\n'; |
| 76 | return 0; |
| 77 | } |
| 78 | //https://www.spoj.com/problems/LCS0/ |