Cod sursa(job #2930820)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 29 octombrie 2022 17:34:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.2 kb
//Suffix Automaton
// By Buta Gabriel-Sebastian (butasebi)
//University of Bucharest

//ATTENTION! Always use sa_init() to reset/initiate the string automaton
// sa_extend(CHAR) to append the character CHAR at the end of the string
// sa_extend_string(STRING)  to append the string STRING at the end of the string
//check_occ(STRING) checks if STRING is a substring of the big string
//nr_subs(STRING) checks the number of different substrings of STRING
//sum_len_subs(STRING) checks the sum of lengths of all substrings of STRING
// kth_subs(STRING, k) finds the k-th substring of the string STRING (k = 0 => empty string)
//smallest_cyclic_shift(STRING) find the smallest cyclic shift of the string
//nr_occurrences(STRING, STRING2) returns the number of occurrences of STRING2 in STRING
//first_occurrence(STRING, STRING2) returns the first occurrence of STRING2 in STRING (returns the position where STRING2 begins (considering STRING indexed by 1))
//all_occurrences(STRING, STRING2) returns all the position where STRING2 occurs in STRING as a vector<int> list, if no occurrence returns empty list (returns the position where STRING2 begins (considering STRING indexed by 1))
//lcs(STRING, STRING2) returns the longest common substring between STRING and STRING2
//EVERYTHING FUNCTION FROM ABOVE IS DONE IN O(length(STRING))
#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable:4996)
using namespace std;
long long ii, tt;
struct state {
    int len, link;
    map<char, int> next;
    int first_occ;
    bool is_clone = false;
    vector <int> inverse_link;
};
const int MAXLEN = 2000000;
state st[MAXLEN * 2];

vector <int> all_occs;
int sz, last;
void sa_init()
{
    st[0].len = 0;
    st[0].link = -1;
    sz++;
    last = 0;
}
void sa_extend(char c)
{
    int cur = sz++;
    //divine_cnt[cur] = 1;
    st[cur].len = st[last].len + 1;
    st[cur].first_occ = st[cur].len;
    int p = last;
    while (p != -1 && !st[p].next.count(c)) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) {
        st[cur].link = 0;
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
            st[cur].link = q;
        } else {
            int clone = sz++;
            st[clone].first_occ =  st[q].first_occ;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            st[clone].is_clone = true;
            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
void sa_extend_string(string A)
{
    for(int i = 0; i < A.size(); i ++)
        sa_extend(A[i]);
}

int dp[MAXLEN * 2], ans[MAXLEN * 2];
bool seen[MAXLEN * 2];

void DFS_all_occs(int state, int len)
{
    if (!st[state].is_clone)
        all_occs.push_back(st[state].first_occ - len + 1);
    for (int new_state : st[state].inverse_link)
        DFS_all_occs(new_state, len);
}

vector<int> all_occurrences(string A, string B)
{
    all_occs.clear();
    sa_init();
    sa_extend_string(A);

    for (int i = 1; i < sz; i ++)
        st[st[i].link].inverse_link.push_back(i);

    bool ok = true;
    int current_state = 0;
    for(int i = 0; i < B.size(); i ++)
        if(st[current_state].next.count(B[i]))
            current_state = st[current_state].next[B[i]];
        else
        {
            ok = false;
            break;
        }

    if(ok == 0)
        return {};

    DFS_all_occs(current_state, B.size());

    return all_occs;
}

vector <int> occs;
string A, B;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void read()
{
    f >> A >> B;
}
void solve()
{
    occs = all_occurrences(B, A);
}
void write()
{
    g << occs.size() << "\n";
    for(int i = 0; i < occs.size(); i ++)
        g << occs[i] - 1 << " ";
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    //cin >> tt;
    tt = 1;
    for(ii = 1; ii <= tt; ii ++)
    {
        read();
        solve();
        write();
    }

    return 0;
}