#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define fi first
#define se second
#define ld double
const int md = 1e9+7;
const int K = 26;
struct node{
int next[K],go[K],link = -1,e_link = -1;
bool leaf = 0;
char pch;
int p = -1;
int id;
node(int p = -1,char ch = '#'):p(p),pch(ch){
fill(next,next+K,-1);
fill(go,go+K,-1);
}
};
vector<node> t(1);
void add_string(string s,int id){
int c = 0;
for(char ch: s){
int v = ch-'a';
if(t[c].next[v]==-1){
t[c].next[v] = t.size();
t.emplace_back(c,ch);
}
c = t[c].next[v];
}
t[c].leaf = 1;
t[c].id = id;
}
int go(int c,char ch);
int get_link(int c){
if(t[c].link==-1){
if(c==0 || t[c].p==0)
t[c].link = 0;
else
t[c].link = go(get_link(t[c].p),t[c].pch);
if(t[t[c].link].leaf)
t[c].e_link = t[c].link;
else
t[c].e_link = t[t[c].link].e_link;
}
return t[c].link;
}
int go(int c,char ch){
int v = ch-'a';
if(t[c].go[v]==-1){
if(t[c].next[v]!=-1)
t[c].go[v] = t[c].next[v];
else
t[c].go[v] = (c==0)? 0: go(get_link(c),ch);
}
return t[c].go[v];
}
void search(char s[]){
int n = strlen(s);
int c = 0;
for(int i=0;i<n;i++){
c = go(c,s[i]);
int cc = c;
while(cc!=-1 && t[cc].leaf){
cout<<i<<" "<<t[cc].id<<endl; // end position and string id
cc = t[cc].e_link;
}
}
}
signed main()
{
string arr[3] = {"a", "aa", "aaa"};
for(int i=0;i<3;i++)
add_string(arr[i],i);
char s[] = "aaaaa";
search(s);
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgbGQgZG91YmxlCmNvbnN0IGludCBtZCA9IDFlOSs3OwoKY29uc3QgaW50IEsgPSAyNjsKc3RydWN0IG5vZGV7CiAgICBpbnQgbmV4dFtLXSxnb1tLXSxsaW5rID0gLTEsZV9saW5rID0gLTE7CiAgICBib29sIGxlYWYgPSAwOwogICAgY2hhciBwY2g7CiAgICBpbnQgcCA9IC0xOwogICAgaW50IGlkOwogICAgbm9kZShpbnQgcCA9IC0xLGNoYXIgY2ggPSAnIycpOnAocCkscGNoKGNoKXsKICAgICAgICBmaWxsKG5leHQsbmV4dCtLLC0xKTsKICAgICAgICBmaWxsKGdvLGdvK0ssLTEpOwogICAgfQp9Owp2ZWN0b3I8bm9kZT4gdCgxKTsKdm9pZCBhZGRfc3RyaW5nKHN0cmluZyBzLGludCBpZCl7CiAgICBpbnQgYyA9IDA7CiAgICBmb3IoY2hhciBjaDogcyl7CiAgICAgICAgaW50IHYgPSBjaC0nYSc7CiAgICAgICAgaWYodFtjXS5uZXh0W3ZdPT0tMSl7CiAgICAgICAgICAgIHRbY10ubmV4dFt2XSA9IHQuc2l6ZSgpOwogICAgICAgICAgICB0LmVtcGxhY2VfYmFjayhjLGNoKTsKICAgICAgICB9CiAgICAgICAgYyA9IHRbY10ubmV4dFt2XTsKICAgIH0KICAgIHRbY10ubGVhZiA9IDE7CiAgICB0W2NdLmlkID0gaWQ7Cn0KaW50IGdvKGludCBjLGNoYXIgY2gpOwppbnQgZ2V0X2xpbmsoaW50IGMpewogICAgaWYodFtjXS5saW5rPT0tMSl7CiAgICAgICAgaWYoYz09MCB8fCB0W2NdLnA9PTApCiAgICAgICAgICAgIHRbY10ubGluayA9IDA7CiAgICAgICAgZWxzZQogICAgICAgICAgICB0W2NdLmxpbmsgPSBnbyhnZXRfbGluayh0W2NdLnApLHRbY10ucGNoKTsKICAgICAgICBpZih0W3RbY10ubGlua10ubGVhZikKICAgICAgICAgICAgdFtjXS5lX2xpbmsgPSB0W2NdLmxpbms7CiAgICAgICAgZWxzZQogICAgICAgICAgICB0W2NdLmVfbGluayA9IHRbdFtjXS5saW5rXS5lX2xpbms7CiAgICB9CiAgICByZXR1cm4gdFtjXS5saW5rOwp9CmludCBnbyhpbnQgYyxjaGFyIGNoKXsKICAgIGludCB2ID0gY2gtJ2EnOwogICAgaWYodFtjXS5nb1t2XT09LTEpewogICAgICAgIGlmKHRbY10ubmV4dFt2XSE9LTEpCiAgICAgICAgICAgIHRbY10uZ29bdl0gPSB0W2NdLm5leHRbdl07CiAgICAgICAgZWxzZQogICAgICAgICAgICB0W2NdLmdvW3ZdID0gKGM9PTApPyAwOiBnbyhnZXRfbGluayhjKSxjaCk7CiAgICB9CiAgICByZXR1cm4gdFtjXS5nb1t2XTsKfQp2b2lkIHNlYXJjaChjaGFyIHNbXSl7CiAgICBpbnQgbiA9IHN0cmxlbihzKTsKICAgIGludCBjID0gMDsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAgIGMgPSBnbyhjLHNbaV0pOwogICAgICAgIGludCBjYyA9IGM7CiAgICAgICAgd2hpbGUoY2MhPS0xICYmIHRbY2NdLmxlYWYpewogICAgICAgICAgICBjb3V0PDxpPDwiICI8PHRbY2NdLmlkPDxlbmRsOyAvLyBlbmQgcG9zaXRpb24gYW5kIHN0cmluZyBpZAogICAgICAgICAgICBjYyA9IHRbY2NdLmVfbGluazsKICAgICAgICB9CiAgICB9Cn0Kc2lnbmVkIG1haW4oKQp7CiAgICBzdHJpbmcgYXJyWzNdID0geyJhIiwgImFhIiwgImFhYSJ9OwogICAgZm9yKGludCBpPTA7aTwzO2krKykKICAgICAgICBhZGRfc3RyaW5nKGFycltpXSxpKTsKICAgIGNoYXIgc1tdID0gImFhYWFhIjsKICAgIHNlYXJjaChzKTsKICAgIHJldHVybiAwOwp9