Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
- using namespace std;
- struct state {
- int len, link;
- int next[58];
- };
- const int MN = 100007;
- state sa[2*MN];
- int sz, last;
- void sa_init() {
- sz = 1;
- last = 0;
- sa[0].len = 0;
- sa[0].link = -1;
- for(int i = 0; i < 58; i++) sa[0].next[i] = 0;
- }
- void sa_extend(int c) {
- int cur = sz++;
- sa[cur].len = sa[last].len + 1;
- for(int i = 0; i < 58; i++) sa[cur].next[i] = 0;
- int p;
- for (p = last; p != -1 && !sa[p].next[c]; p = sa[p].link) sa[p].next[c] = cur;
- if (p == -1) {
- sa[cur].link = 0;
- } else {
- int q = sa[p].next[c];
- if (sa[p].len + 1 == sa[q].len) {
- sa[cur].link = q;
- } else {
- int clone = sz++;
- sa[clone].len = sa[p].len + 1;
- for (int i = 0; i < 58; i++){
- sa[clone].next[i] = sa[q].next[i];
- }
- sa[clone].link = sa[q].link;
- for (; p!= -1 && sa[p].next[c] == q; p = sa[p].link) {
- sa[p].next[c] = clone;
- }
- sa[q].link = sa[cur].link = clone;
- }
- }
- last = cur;
- }
- vector<int>d(MN,0);
- long long conta_substrings(){
- long long ret=0;
- for( int i=1 ; i<sz ; i++ ){
- ret +=sa[i].len-sa[sa[i].link].len;
- }
- return ret;
- }
- void ext(char i){
- sa_extend(i-'A');
- }
- int main() {
- optimizar_io;
- int num;
- cin >> num;
- while(num--){
- string line;
- cin >> line;
- sa_init();
- for_each (line.begin(), line.end(), ext);
- int um = conta_substrings();
- string seg;
- cin >> seg;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement