# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
367995 | SeekingOblivion | Round words (IZhO13_rowords) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#define fin cin
//#define fout cout
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n,st,f[26],i,St[4010],Dr[4010],m;
char c[4010],s[4010];
vector<int> aint;
struct Nod{
char val;
int f[26];
} blanc;
vector<Nod> v;
vector<int> l[4001],car[27];
void add(int p,int en,int nod)
{
int next;
if(v[nod].f[c[p]-'a']==0)
{
next=v.size();
blanc.val=next;
v.push_back(blanc);
l[nod].push_back(next);
car[c[p]-'a'].push_back(nod);
}
else next=v[nod].f[c[p]-'a'];
if(p!=en) add(p+1,en,next);
}
void dfs(int nod)
{
St[nod]=++m;
for(auto it:l[nod]) dfs(it);
Dr[nod]=++m;
}
int main()
{
ios_base::sync_with_stdio(false);
fin>>c+1>>s+1;
for(n=1;c[n];n++);
n--;st=1;
v.push_back(blanc);
for(st=1;st<=n;st++)
{
add(st,st+n,0);
c[st+n]=c[st];
}
dfs(0);
aint.resize(m+1);
for(i=1;s[i];i++)
{
for(auto it:car[s[i]-'a'])
{
update(1,1,m,st[it],1);
update(1,1,m,dr[it],1);
}
}
return 0;
}
//https://oj.uz/problem/view/IZhO13_rowords