fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+5;
  4. struct trie
  5. {
  6.     int child[26];
  7.     int exist,cnt;
  8. };
  9. int cur=0;
  10. trie node[N];
  11. void set_root()
  12. {
  13.     for(int a=0;a<26;a++){
  14.         node[0].child[a]=-1;
  15.     }
  16.     node[0].exist=0;
  17.     node[0].cnt=0;
  18. }
  19. int new_node()
  20. {
  21.     cur++;
  22.     for(int a=0;a<26;a++){
  23.         node[cur].child[a]=-1;
  24.     }
  25.     node[cur].exist=0;
  26.     node[cur].cnt=0;
  27.     return cur;
  28. }
  29. void build(string s)
  30. {
  31.     int pos=0;
  32.     for(int a=0;a<s.size();a++){
  33.         int c=s[a]-'a';
  34.         //cout<<c<<" ";
  35.         //cout<<node[pos].child[c]<<"\n";
  36.         if(a==0) node[pos].cnt++;
  37.         if(node[pos].child[c]==-1){
  38.             node[pos].child[c]=new_node();
  39.             node[pos].cnt++;
  40.         }
  41.         pos=node[pos].child[c];
  42.         if(a==s.size()-1) node[pos].cnt++;
  43.     }
  44.     node[pos].exist++;
  45. }
  46. int main()
  47. {
  48.     /*ios_base::sync_with_stdio(false);
  49.     cin.tie(0);
  50.     cout.tie(0);*/
  51.     int n;
  52.     while(cin>>n){
  53.     //cin>>n;
  54.         string s[n];
  55.         set_root();
  56.         for(int a=0;a<n;a++){
  57.             cin>>s[a];
  58.             build(s[a]);
  59.         }
  60.         double sum=0;
  61.         for(int a=0;a<n;a++){
  62.             int pos=0;
  63.             for(int b=0;b<s[a].size();b++){
  64.                 //cout<<node[pos].cnt<<" ";
  65.                 if(node[pos].cnt>1) sum++;
  66.                 pos=node[pos].child[s[a][b]-'a'];
  67.             }
  68.             //cout<<"\n";
  69.         }
  70.         cout<<setprecision(2)<<fixed<<sum/(double)n<<"\n";
  71.     }
  72. }
  73.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
22
message
is
articles
id
start
person
number
conditions
now
sale
why
rights
write
part
groups
get
model
release
software
application
s
de
7
american
both
just
meeting
previous
another
always
28
little
h
guide
based
general
men
development
set
rights
world
stores
customer
market
board
e
june
login
computer
just
she
v
play
years
reviews
left
l
place
why
7
books
future
systems
but
april
sell
free
11
war
page
you
related
s
id
find
learn
password
not
additional
25
offer
previous
books
young
science
thread
english
like
yes
of
without
even
january
become
posted
history
students
court
financial
power
john
issue
red
yet
details
5
i
let
want
issue
been
21
server
man
re
internet
medical
committee
view
hotel
articles
texas
training
department
user
please
date
our
request
something
after
social
november
21
read
product
questions
date
all
application
march
when
b
april
video
sports
was
will
care
she
know
job
on
if
case
22
project
guide
software
resources
room
key
training
per
blue
high
september
into
county
library
she
post
save
d
experience
up
free
message
23
where
include
family
black
prices
future
young
has
request
days
hard
read
phone
united
star
day
two
dec
accessories
one
h
view
services
15
service
february
compare
however
where
local
things
has
above
contact
about
three
pictures
building
based
23
tv
down
next
version
single
series
california
e
major
article
make
windows
rights
form
york
request
been
english
then
r
human
security
month
25
contact
v
start
story
r
provided
most
possible
insurance
comment
offers
location
must
states
required
night
between
give
questions
standard
property
go
out
systems
web
17
center
staff
this
forum
feedback
action
think
days
credit
money
mobile
question
light
tv
press
cost
info
25
what
yet
street
did
terms
account
few
application
code
full
shopping
research
million
return
la
posted
between
very
comments
provide
man
new
service
financial
results
20
site
law
text
great
last
rights
market
complete
box
november
top
again
same
need
add
above
even
said
against
field
29
above
problem
any
top
yahoo
market
features
like
east
research
based
address
four
think
better
standard
tax
had
home
terms
following
two
directory
phone
this
areas
day
call
of
14
even
stock
phone
state
account
life
sports
within
please
jan
non
may
e
thread
4
have
policy
z
found
24
as
latest
line
compare
month
version
share
january
forum
through
system
meeting
feedback
web
let
link
added
looking
before
united
o
these
social
w
22
water
different
say
to
left
law
was
al
provided
program
b
application
x
north
including
i
girls
home
at
jobs
movies
research
4
english
dvd
going
high
12
friend
money
meeting
tools
my
sports
food
conditions
good
hard
title
november
15
found
may
has
company
forum
new
x
title
pay
browse
out
posts
must
web
also
17
history
interest
time
end
high
rss
china
more
power
have
issue
map
who
the
usa
product
show
2
advanced
network
27
quality
questions
going
area
play
compare
memory
tools
following
offer
sports
given
changes
been
accessories
by
take
part
save
data
he
in
required
news
would
needs
resources
28
reserved
new
great
care
members
pc
create
without
two
science
small
share
times
are
forum
san
again
this
different
park
body
code
week
i
questions
by
can
left
7
health
issues
user
service
business
gift
art
2
re
black
24
found
medical
required
conditions
has
additional
way
seller
nov
rates
stock
photos
related
then
research
who
thread
within
print
security
state
cd
issues
like
18
status
technology
share
start
as
access
college
save
accessories
found
against
t
again
members
in
guide
would
current
16
major
sex
accessories
sites
play
features
department
similar
review
case
browse
student
test
latest
south
type
22
language
week
online
prices
yahoo
contact
between
pay
just
march
private
he
live
has
us
pm
media
different
offers
market
working
blog
2
size
york
30
register
z
same
experience
time
something
set
with
life
english
id
women
source
were
s
did
include
think
fax
order
west
cd
days
committee
box
audio
under
memory
products
version
20
share
library
quote
latest
california
my
information
provided
off
time
required
property
action
o
advanced
rss
given
space
act
who
11
text
would
section
stores
application
ebay
many
online
software
u
request
stdout 
1.86
1.43
1.79
1.86
1.18
1.76
1.20
1.67
1.57
1.41
1.70
1.67
1.65
2.04
1.71
1.76
1.80
1.86
1.57
1.00
1.79
1.45
1.00
1.58
1.40
1.76
1.00
1.74
1.75
1.00
1.00
2.00
1.89
1.56
1.95
1.00
1.73
1.65
1.27
https://ideone.com/uT3ZvC
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!