Pagini recente » Cod sursa (job #549451) | Cod sursa (job #2826907) | Cod sursa (job #2383767) | Cod sursa (job #873163) | Cod sursa (job #2930821)
//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>
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]);
}
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()
{
//cin >> tt;
tt = 1;
for(ii = 1; ii <= tt; ii ++)
{
read();
solve();
write();
}
return 0;
}