Author: vacancy

本Tag来源于我与Freda同学的一段日常对话,我问她,这事儿,你知道吗?

题材敬告:本文的内容多涉及人工智能,神经网络,计算语言学。

(2018-06-05) #你知道吗#1:\(\tanh(x)\)的导数是\(1 – \tanh^2(x)\)。因此在神经网络优化中使用\(\tanh\)做激活函数可以在反向传播时计算非常高效。

(2018-06-05) #你知道吗#2:\(\tanh(x) = 2 \sigma(2x) – 1\),其中\(\sigma\)是Sigmoid函数。

(2018-06-05) #你知道吗#3:Distributional Vector和Distributed Vector是不同的两个概念:Distributional是指真·PMI矩阵,而Distributed指的是Word2Vec等模型。当然Levy et.al. 的paper证明了两者的(在一定条件下的)等价性。

(2018-06-11) #你知道吗#4:数词不止有One, Two, Three那么简单。Quoted from wiki:

Numerals are often conflated with other parts of speech: nouns (cardinal numerals, e.g., “one”, and collective numerals, e.g., “dozen”), adjectives (ordinal numerals, e.g., “first”, and multiplier numerals, e.g., “single”) and adverbs (multiplicative numerals, e.g., “once”, and distributive numerals, e.g., “singly”).

(2018-10-02) #你知道吗#5:Language Model中最常用的评价指标之一Perplexity的发明者是Jelinek et al. 1977. “Perplexity – a measure of the difficulty of speech recognition tasks”. Cited by 171 (as of 2018-10-02).

(2018-10-26) #你知道吗#6:”a priori”和”prior”是两个(在意思上没有什么关系的)词。”a priori”合起来是一个词,形容词属性,表示“显然的”。而“prior”是名词属性,表示“先验(分布)”,一般用在Bayesian的上下文中,和“posterior”对应。另外“an a priori prior”意思是:“一个显然的先验分布”。 // 经过了长达两周的纠结,我们终于搞清楚了这两个词的意思。

「旧忆就像一扇窗,推开了就再难合上。」

那些记忆在脑中开始循环播放。我提笔,泪湿眼眶。

1.
对世界的认知和记忆大概从初中开始。那些个温暖的场景总是难以忘却。
比如,一个阳光正好的午后,你撒着汗水跑向她,她回眸对你一笑。你轻轻拭去她不小心落在手心的西瓜汁。或是,你终于把头轻轻靠在她的肩膀。
又如,一个风起的秋日,她的帽檐尴尬的撞在你的额头上,你一笑。
再如,一个有些寒冷的冬日,你将她抱起,盘旋。
最终你离开了她,5年之后,你看着她的影子,告诉自己都是往昔。

2.
初中一年级的时候,你最喜欢吃方便面。你无忧无虑的。翘了课,和同学一起坐在那个公交车站前的冰冷的座椅上,端着一碗热腾腾的面。你知道他是你永远的朋友。
初中三年级的时候,你们换了新的校区,每天放学和你一起吃东西的人换了几个。你们喜欢吃章鱼小丸子,每次都能吃掉好多。你们最喜欢讨论的话题是爱情。那些说不离不弃的,最后还是离散了。
就像每年的春节,你都会给他们发去一条祝福的短信。这么多年,你终于还是没有走出念旧的套路,就像许嵩感慨的,“你没想象中那么恋旧”。一年年的回复,从感慨还是变到了,“都多大的人了”。你知道他们长大了,你还是没有。

3.
初中二年级的十四岁生日,你没有一点点想哭。你还是轻狂的年纪。那时的你不会猜到那件文化衫可能是你最后一次自己作画,那些人和那些歌谣,可能再也不会听见。那些在简陋的上下铺里的彻夜聊天,终究是被冠以“天真无邪”而被时间作了淡出特效。
最后中考那一天,出来的时候,你没有什么难过,你根本没有意识到一个时代结束。幸好你很忙,忙着做毕业纪念视频,忙的你都来不及细细怀念一下。你不知道下一次你怀念起来这些,已是一切都湮灭不复返。

4.
你曾说你不喜欢你的高中,它没有给足你你要的自由。直到后来你才明白那些真正对你好的人是多么喜欢你。
你应还记得无数个月朗星稀的晚上,你逃开了晚自习,去那幢小楼里玩音乐。
你应还记得那年5月的时候,你和学长们一起奋斗着。你可能没有什么危机感,那可能是你不知道,每件事情这一次做,就是最后一次做了。下一次再怎么做相同的事,都是物是人非了。
13年9月是你最迷茫的日子,你不知道自己能做什么,你还在混着过,和老师捉迷藏。此刻你终于理解了那个说话不紧不慢的老教师,他悠悠地说着,就像时光的河静静淌。你突然有点想给他挂一个电话,给他背一首,你喜欢的诗了。那个总是护着你的班主任,她现在还好吗,突然的感激之情竟然不知从何说起。谢天谢地,那些人终究是爱你的。

5.
你看着爸妈年轻时抱着你的模样,终究还是落泪了。
他们一定把最好的给了你。再回去看看他们吧,下一次有机会,都不知道是何时了。

6.
从5年前你就嚷嚷着,你站在青春的尾巴上。这条尾巴越来越长。
你还是年少轻狂的,你还是单纯善良的,你还是小心翼翼的。可是你却被迫着明白了,过去的事情就是过去了。你明白了,“等以后我~了,我一定~。”是一纸荒唐。
就在歌声里肆意地落泪吧。

 

故梦终。终究那些年华都付作过往。

写下这篇博文的目的,似乎是为了记录自己生活里的场景,不愿意看我杂乱异常文字的人,取走自己所爱的歌便好。
记得两年前我曾写下博文:2012-2013:那些温暖我的音乐,可是由于一些技术上的原因,我似乎将那篇文章不小心删除了。想来也是有些难过。所谓2014-2015,更准确的来说是自己大一这一年。我选择用音乐来帮助我回忆起这些生活。

1. 《芊芊》(作曲:胜屿,作词:叶铭秋,演唱:回音哥)
绝唱一段芊芊 / 爱无非看谁成茧 / 和你对弈输赢都回不去
一曲轻描淡写勾勒尽是我的呼吸 / 山穷水绝处回眸一遍你

在许多个北漂的夜里,我借此歌慰藉自己。回念与你相依,竟已是多年之前。很高兴再次遇见你之时,你眉间的清秀仍未更改,已经长成大姑娘的你。
那就让我守住回忆里的你吧,它竟然已像儿时的故事一般让我感到不真切了。每次听到“和你对弈输赢”的时候,都想起那个时候年轻锋芒毕露的自己。日常里,你教会了我很多,让我大开眼界,希望我也是,大概这也是我依恋你的原因吧,你时常让我感到很惊喜。
时至今日,我觉得我离放下你已经不远了,我可以一个人对自己安然若素地讲故事。只是在自己面临崩溃和迷茫的时候,还是能想到你。分手的时候,我说,背过身我先走,如今我终于迈开了脚下的步伐,你也已经走得好远。不过幸好,我还能在行至水穷处的时候,回看你一眼,以你当时给我的鼓励和动力,告诉自己要变得更好。
也许你还是会很讨厌这样的我,但是请相信我在向着做更好的自己在努力。谢谢你留给我的背影和记忆里不会改变的昔时的你。我不会再说爱你了,祝愿你一定要幸福。

2. 《杏花弦外雨》(作曲:潇梦临,作词:若紫鸢,演唱:西国之海妖、CRITTY)
当一阵阵临窗雨 / 洗旧那时心绪 / 曲中人远隔千里万里
不知不觉的停笔 / 留下余韵待续 / 就在那片烟波外 淡成了迤逦

这首歌陪伴了大一新生军训时的我。那时的我刚刚来到北京,来到一个不熟悉的环境,经历一场自己也不知会怎样的军训。在休息的时候,不用训练的时候,我时常戴上耳机,开始播放这首歌。曲调优美,让我便忘记了自己的不知所措。
也曾有几个月朗星稀的夜里,我走在路上听起这首歌,或是站在阳台上看一眼天空。流水声和熟悉的调子让我想到江南水乡,也是我成长的地方。有些骨子里的柔情,或许便是源于这样秀丽的地方吧。

3. 《湘桥月》(作曲:Mzf小慕,作词:口袋易百,演唱:银临、鸦青)
遥望湘桥的月 / 自顾自盈缺 / 伊人独憔悴
我痴痴 / 等你归 / 历尽了风雪 / 才知蹉跎岁月

听到这首歌,是我在北方经历的第一个深秋。暖气的热量还没有那么足,户外北风凌冽的的时候,我骑车在校园里,耳机里播放这首音乐。那时的我,心情平淡,没有很大的课业压力,甚至经常在宿舍里无所事事。我认真地写每一份作业,看该看的书,唯独缺少了一些乐趣,这大概便是我第一次适应大学这样生活的结果。

4. 《混沌》(作曲:丢子,作词:EDIQ,演唱:流月Ryutsuki)
我生于混沌中 / 你应当读懂我的心痛 / 持着利斧欲劈开爱恨朦胧
待战火燎原后 / 生死难与共 /方知此情有多重

霸气的声线,与一个红颜的武侠故事。

5. 《好梦如旧》(作曲:李峻一,作词:并瓦,演唱:HITA、林斜阳)
若长相守不过你拈花我把酒 / 酒醒后能否赏我个好梦如旧
你不先去怎知我相随在后 / 红尘白雪世上一走

6. 《春》(卢亮辉,民族管弦乐作品,高雄市立国乐团演奏)
那是一段愉悦的时光,在一门中国传统音乐鉴赏的课上,我们和老师一起听了这首作品。我还记得,我们曾一起在课上打太极,在课后你给我们讲你的故事,给我们鼓励。
现在我在音乐里听到了,那些,万物复苏的声音。

7. 《WINGS ~TYPE-MOON Fes. – 10th Anniversary – Opening Theme~》(深澤秀行,纯音乐作品)
我在2015跨年的那一天,听到了这首歌。我将它作为起床铃声至今。小提琴听到我泪流满面。
2015年1月,我面临在大学的第一个期末,没有动力。呆在寝室里晒太阳之时,它曾寄予我能量。

8. 《咏春》(作曲:何亮,作词:花晶晶,翻唱:玄觞、倾夜)
春知晓梦不觉恰似你我那年 / 不经事却说离别
燕归来莺语乱谁在歌咏春天 / 眼清澈笑容无邪

我在清华园开春的时候,听着鸟语花香,听到这首歌,画面太美。

8. 《花间旧事》(原曲:小旭音乐-《西狂》,填曲:墨雅,填词:琉璃夭,演唱:小千,京剧表演唱:王萌)
等回忆重温又凉 / 还似旧模样 / 依稀他当年无双 / 不如相忘
再一曲终章 / 看过往,尽泛黄 / 待散场,无人解红妆

若说我最喜欢的句子,应当是戏腔的那句,「寸心一株清明雪,折予赠君寄来生。」

9. 《小时候》(作曲:少司命,作词:落雁知秋,演唱:少司命)
小时候的你如今已何去何从 / 淡淡的月光还在屋檐外朦胧
肥皂泡在空中 / 时光它太匆匆 / 无声的岁月偷走我 / 好多的梦

它能让我想到,美好的事情!小时候,我大概也是这样,穿梭在一个个弄堂巷子里,玩着很简单的玩具,现在才明白那样的无忧无虑,是如此的快乐。

9. 《To the beginning》(作曲:梶浦由记,作词:梶浦由记,演唱:Kalafina)
闭ざされた憧れは / まだ远くへ暗の中
君と生きた日々のすべて / 优しい歌

10. 《Strength of A Thousand Men (Dubstep Remix)》(Two Steps from Hell)
7月的时候,我开始了一段实习经历,这首歌,也是我工作时的战歌。

写在后面:
大一第二学期我没听歌没干活,那我都在干什么呢?
其实我不也知道。

回音哥 – 芊芊

{那是我拥有的,最美好的,小时光}

大约是从高三起,我习惯了在手机中放上很多音乐,然后一遍遍听,留下自己喜欢的几首,按照不同月份收藏一个文件夹。那时候听歌就是在教学楼、食堂、寝室的三点一线上,从霜降走到深冬,再走回一个全新的夏天。

我大约是一个乐于怀念的人,面对逝去的东西会产生无法抵抗的回忆漩涡,愈陷愈深甚至到梦境中都反复见到。这般无法面对离别的我也不知何时才会悔改,或是崩溃。

我翻阅听过的歌。一个个文件夹,就像再一次,走回那年的路。音乐似乎是和记忆里的场景不那么相应的,不过也无妨。食堂到寝室间那段时常积起落叶的路大概是出现频率最高的场景。有一副太阳初升时落叶飘落的画面,有一副冬季日落后寒风瑟瑟的画面。高三那年我走了无数次那条路,在上面留下了关于无穷无尽的苦难生活的感叹。在那条路上,我每次都走得很慢,一边思考一边听音乐,听完大半首歌才能走完不到100米的路。走过这段路,是几幅温暖的阳光下彻的寝室窗口的场景,和几幅熄灯后夜聊谈笑风生的场景。思绪至此,我也终于明白自己放不下的是那些自己度过的时光,那些与我一起度过时光的人,还有那些时光里,我坚定决绝的目标。

选择上中的时候,我以一个“严格要求自己”的理由说服了自己和家人。军训之后,我给自己定下的最多的目标是,慢慢地过生活,慢慢地,无论别人有多急。明明是贪睡的我却一直没有因为想要睡觉放松了自己“松散”的生活方式。认真刷牙,认真洗脸,认真收拾所有的物品,让一切都显得我100%从容面对。我想我高中三年应该成功地做到了这一条。

高三的时候我应该与父母发过不少的脾气。尤其是母亲。她真正地陪着我一路成长,也没少受我的气。我愈发明白自己从小到大都是一个好强的人,就算一个成绩明明无关紧要却也不想输给别人。高三结束后我和母亲聊天说,现在想想,高三还是挺轻松的。母亲回应说,才不是呢,那时候看你都觉得辛苦,你脾气又不好。

从并不遥远的北京回来,再次见到母亲,突然感觉到她真的是老了。记忆里在某个破旧的巷弄里,某个油腻的灶间里劳动奔波的母亲已不复当年的容颜了。她现在拥有了稍微舒适一些的生活,她终于把我教育成了一名知名大学的学生,她可以有足够的宣传育儿经验的资本,但是我却离开她了。她时常嘘寒问暖,时常发自己聚会的照片。她会给我买很多很多的衣服和日用品等着我回来。每次收到消息的时候我却只想骂自己一句,为什么又几天没有往家里打电话了。因为军训那次向家里的联络里,家人的那份欣喜,我大概永远忘不掉。

小时候上幼儿园的时候,我说妈妈我会想你的。现在轮到她向我说,儿子,妈妈想你了。记得儿时父母吵架的时候,她曾和我说,妈妈在这里无依无靠只有你了,她就一直陪着我走过了18个严冬和酷暑。而今我离开她飞了。

后来我终究还是没有后悔选择了上中,至少我在那里遇到了那些老师和那些同学。那些会和我促膝谈心,放下高高在上的权威的老师,那些会想一个朋友一般与我交谈的,甚至向我学习的老师,那些理解宽容我的生活甚至纵容我的任性的老师,还有那些让我感动到羞愧无数次的老师。一样不可忘记的还有那些同学,无数个深夜里和我聊天的你们。正是和你们在一起的日子,我感受到友谊满满溢出的不可名状的幸福感。如今你们也远去了。

今天我回到上中了。老师们也老了。同学们也不再能朝夕共处了。那些过往的经历便因此变得刻骨铭心起来。我好想一口气把所有的记忆写下来,以免有一天我糊涂到忘记了这一段。

不知不觉就写到了这里,最后我突然很想写那个我从来没有听过他话的语文老师。他似乎有那么样一种魅力,他笑起来的时候,能有一种让人安静下来的力量。大概是他本就是一个安静的人吧,区别于那些语速匆匆的老师,他每一句话都是淡淡的,慢慢的,却不失力量。

我想我也该成为这样的人。

在高考那会,我曾在酒店里、路上循环这一首歌。它是我高考记忆的一部分。里面有我考前的超越言语的紧张,有我语文结束后流下的无尽的泪水,有我考后突然下坠的失落。重要的是,每次我听起这首歌,我还能想起那些年我耳机里循环这首歌时候,身边的人。

歌词唱道,无你处,无江湖。

少司命 – 烟笼长安

先回忆两个基本知识点。

  • 母函数:就像是二项式展开,(x+y)^n,可以表示n个物品(分先后)用两种颜色染色,方案数是多少。
  • Polya定理:本质上是Burnside引理的进一步延伸,其中color^c(g),c(g)表示循环节个数,求的就是不动点的个数,可以理解为在同一个循环节中所有的元素必须染成相同颜色。

那么将两者结合在一起,考虑一个置换g。

  1. 对于其中的一个长度为i的循环,染色方法用母函数表示出来就是(r^i+g^i+b^i),原因是这i个元素必须用同一种颜色染色,因此不是(r+g+b)^i!
  2. 然后考虑若干个不相交的置换,那么直接将他们母函数相乘。
  3. 最后对所有置换求母函数的乘积,就可以得到答案。

例题解释。9颗珠子一个环,两种颜色染色,问6黑3白的染色方法数是多少。

  • 循环:(x + y)^9 + (x^3 + y^3)^3*2 + (x^9 + y^9)*6
  • 翻折:1个单元素,4个双元素,(x + y)*(x^2 + y^2)^4*9
  • 最终答案:x^9 + x^8 y + 4 x^7 y^2 + 7 x^6 y^3 + 10 x^5 y^4 + 10 x^4 y^5 + 7 x^3 y^6 + 4 x^2 y^7 + x y^8 + y^9

完美解决。

感谢:
myc老师对我一年多来的指导,如果没有您,我现在还是一个门外汉,是您告诉了我进入音乐世界的一条缝隙。在制作的过程中,您一次次帮我审稿,手把手叫我作编曲,在百忙之中为我完成了正式的编曲工作,真的非常感动!
zxy童鞋从文委告诉我们这次活动时开始一次次认真的写词,我已记不清你交给我的初稿有多少,我们一起改过的版本有几个,感谢你为我们压榨的文艺细胞(PS. 以及对你的拼接能力表示深深的震撼!)。如果有机会你说的梦想能成现实,我们都愿意付出努力。
Mr.Escape童鞋时刻围绕在我和xy同学身旁,为我们出谋划策,你是绝佳的producer,另外祝你SAT考试顺利!
还有感谢所有参与演唱和排练的同学(按出场顺序):zxy, Tianyuan, Mr.Win, Mr.Desire, Ms.Orchid, AID, GUO Shengjie。虽然我们没有拿到第一,但是你们都是最棒的!这个边练习边录音的版本,也当做寒假和新年的礼物送给你们!
还有感谢所有支持我的SHSTV的老师们,周老师和英俊哥你们俩的建议总是那么犀利,还有涛哥胡老师你们的关心!
最后感谢董老师,谢谢你在高一一年对我的关心,谢谢你在比赛时给我的鼓励,一直很想告诉你,谢谢你!

2013年1月24日,《记得》,网络首发。

记得
上海中学 2014届9班

曲 / 歌澈
词 / 花十九

知了不停叫,不停叫思念
想念小树林露天的午餐
盛夏快过去,快过去这里
明天我就想出发去见你

黑板上的日期,熟悉的课桌椅
我们剩下的也只有回忆
骑单车去旅行,是我们的约定
年少无知还是很坚定

再见面的时候你是否记得我
记得我们曾经邂逅的走过的路口
记得还没来得及,交换会的日记
写满了我和你所有的过去
再见面的时候你是否记得我
记得我们曾经约定的远方的旅行
记得我们投硬币,决定要去哪里
会不会,下一站,就和你相遇

说好要再见,要再见太远
只能够看看你的明信片
记得那一年,那一年雨天
伤心的时候有你在身边

在走廊上涂鸦,背包里藏漫画
习惯了和你在一起罚站
上课时说闲话,下课后奔食堂
无忧无虑的年少时光

再见面的时候你是否记得我
记得我们曾经欢笑的流泪的赛场
记得你撒过的汗,我成真的梦想
谢谢你陪着我去拼搏去闯
再见面的时候你是否记得我
记得我们曾经写过的唱过的歌谣
记得耀眼的舞台,青春在闪着光
这一刻是不是会变成永远

开夜车的时候总是害怕宿管
周爽分数出来之后让我们很沮丧
第五节课的铃声,它显得特别慢
刷刷题 奔奔饭 一天又一天
在上中的时光我永远不会忘
校园里银杏的落叶它年复一年
每个角落都怀念
总觉往事如烟
不变的是我们是龙门的人

前言
完成如下概念的认识:自动机,状态,转移函数。这些都是相关的理论,可以参看黑书或者算法导论等。

分析

  1. Reg(s) 表示s这个状态能够接受的字符串的集合。
  2. Right(s) 如果a在S[l, r)出现,则它能够识别从r开始的后缀。
    Right(s) 是一个集合,表示所有S[l, r)中的r。
    有了Right(s),只要给出字符串长度len,就能确定所有串。
    len一定是一个区间,我们称之为[Min(s), Max(s)]。
  3. 可以证明 Right(s) 只有独立和包含关系(这就证明了总复杂度是O(n))的。
  4. Right就构成了一棵树,令Parent(s)表示其祖先,称这棵树为Parent树,Parent(s)表示包含s状态的Right集合且最小的状态。
  5. 为什么Min(s) – 1不行? 因为出现位置超过了Right(s)了。那么Max(Parent(s)) = Min(s) – 1。
  6. 考虑转移f(s, c) = t,那么由于多了一个字符c,s的Right集合中,只有S[ri] = c才能符合条件。
    所以t的Right集合是 {r_i+1 | s[r_i] == c}。
    而且有一个显然的推论:Max(t) > Max(s)。
  7. 令fa = Parent(s),若s有出发标号为x的边,那么fa也有,且Right(f(s, c)) 包含于 Right(f(fa, c))。

构造

  1. 这是一个在线构造法。
  2. 设源串是T,新字符是x,则新串是Tx。
  3. 考虑Right集合中包含Len(T)的集合,v1, v2, …, vk
    必然存在一个Right(p) = {L} 的节点p(f(T)),那么v1, v2, …, vk都可以用Parent函数找到。
  4. 构造新状态Right(np) = {L+1}
  5. 不妨我们假设v1 = p, v2 = Parent(v1), …, vk = root。
    考虑一个v的集合Right = {r1, r2, …, rn = L},
    如果在它后面加字符x的话,新状态nv只有s[ri] = x才满足。
    我们知道,如果vi没有出发指向x的边,那么就没有这样的ri。
    而我们又知道,如果vi有x的边,那么所有vi+1也有。
  6. 对于没有到x的边的,连一条到np的边。
  7. 令vp是第一个有x边的状态。考虑其集合Right(vp) = {r1, r2, r3, …, rn}。
    令q = f(vp, x),
    如果Max(q) 恰好等于 Max(vp) + 1,那么直接把Parent(np)设为q;
    否则,就说明会新建点,我们新建点nq,Right(nq) = Right(q) ∪ {L+1},
    则,Parent(q) = nq(q是nq的真子集),
    并且Parent(np) = nq,
    由于区间包含等等等关系可以证明Parent(nq) = Parent(q)。
  8. 由于转移的时候结束位置是不起作用的,所以f(nq, *) = f(q, *)。
    最后,我们需要把所有f(vi, x) = q的点全部指向nq。

代码

const int MaxNode = 10000;
const int MaxChar = 30;

int go[MaxNode][MaxChar];
int val[MaxNode], pnt[MaxNode];
int chr[MaxNode];
int init, last, tot;

inline void init_automachine(void) {
	last = init = tot = 1;
}

void extend_automachine(int c) {
	int p = last, np = ++tot;
	val[np] = val[p] + 1; chr[np] = c;
	while (p && go[p][c] == 0)
		go[p][c] = np, p = pnt[p];

	if (p == 0)
		pnt[np] = init;
	else {
		int q = go[p][c];
		if (val[p] + 1 == val[q])
			pnt[np] = q;
		else {
			int nq = ++tot;
			val[nq] = val[p] + 1; chr[nq] = c;
			for (int j = 0; j < MaxChar; ++j)
				go[nq][j] = go[q][j];

			pnt[nq] = pnt[q], pnt[q] = nq, pnt[np] = nq;
			while (p && go[p][c] == q)
				go[p][c] = nq, p = pnt[p];
		}
	}

	last = np;
}

int main(void) {
	freopen("suffix_automachine.in", "r", stdin);
	freopen("output.txt", "w", stdout);

	int T;
	scanf("%dn", &T);

	char s[10000], t[10000];
	for (int i = 0; i < T; ++i) {
		gets(s), gets(t);

		int n = strlen(s), m = strlen(t);
		init_automachine();
		for (int i = 0; i < n; ++i)
			extend_automachine(s[i] - 'a');

		int ans = m;
		for (int i = 0, cur = init; i < m; ++i)
			if (go[cur][t[i] - 'a'] != 0)
				cur = go[cur][t[i] - 'a'];
			else {
				ans = i;
				break;
			}
		cout << ans << endl;
	}

	return 0;
}