Forwarded from dnaugsuz
谈到这个，有没有人能做一个利用字典匹配这个图里所有可能（横竖排）的连续单词序列的算法... 并算出它的复杂度.... 😶
#oi 打算出个算法题给大家练习下基本功（我才不会告诉你们只是想知道 Google 那张图里有几个单词） 🌝
标题：
灵梦与字母币
题目介绍：
众所周知，幻想乡的巫女小姐，博丽灵梦，是个财迷
在某个夜空格外晴朗的一天，灵梦正坐在博丽神社里喝茶，突然天上掉下来一块陨石砸到了地板上，地板破了一个洞
灵梦注意到洞里有一些硬币（非常幸运！）她赶快把所有找到的硬币都拿了出来，把其中一部分排成一排
Yukari
众所周知，灵梦很贪财，但是也很无聊，于是她很快拿出神社的大字典（有这个东西吗？）(划掉)
在横竖排中开始寻找在字典里出现的词组
字典的第一面有以下四个词组（我也不知道为什么只有四个）：
+ YUKARI
+ RAN
+ MARISA
+ PATCHOULI
灵梦发现了前三个词组，但硬币还有很多，你能帮她找到剩下的词组吗？
提示：
这道题会给你一个字母矩阵和一个字符序列列表，让你在矩阵里寻找所有匹配序列和起始位置，横竖向搜索
例如，字典包含 LM 序列
L M
G J
输出 0(y/r) 0(x/c)
M L
G J
输出 0(y/r) 1(x/c)
限制：
+ 内存：10M
+ 时间：1s
输入格式：
输入分两部分，第一部分是字典，一行一个单词，以一个空白行结束
第二部分是矩阵，矩阵以空格切分，每个项目都是字符，换行则代表记录下一列
输入保证不会出现同一个单词出现在一个以上不同位置的情况
输出格式：
按输入时单词排列的顺序输出序列打印找到的序列起始列号和行号，如果没找到，打印 n，一行一个数据
输入示例：
标题：
灵梦与字母币
题目介绍：
众所周知，幻想乡的巫女小姐，博丽灵梦，是个财迷
在某个夜空格外晴朗的一天，灵梦正坐在博丽神社里喝茶，突然天上掉下来一块陨石砸到了地板上，地板破了一个洞
灵梦注意到洞里有一些硬币（非常幸运！）她赶快把所有找到的硬币都拿了出来，把其中一部分排成一排
Y A X P M I灵梦突然从硬币排列里看到一个单词：
U C L W A D
K S N A R M
A F R A I L
R O P G S S
I J K E A E
Yukari
众所周知，灵梦很贪财，但是也很无聊，于是她很快拿出神社的大字典（有这个东西吗？）(划掉)
在横竖排中开始寻找在字典里出现的词组
字典的第一面有以下四个词组（我也不知道为什么只有四个）：
+ YUKARI
+ RAN
+ MARISA
+ PATCHOULI
灵梦发现了前三个词组，但硬币还有很多，你能帮她找到剩下的词组吗？
提示：
这道题会给你一个字母矩阵和一个字符序列列表，让你在矩阵里寻找所有匹配序列和起始位置，横竖向搜索
例如，字典包含 LM 序列
L M
G J
输出 0(y/r) 0(x/c)
M L
G J
输出 0(y/r) 1(x/c)
限制：
+ 内存：10M
+ 时间：1s
输入格式：
输入分两部分，第一部分是字典，一行一个单词，以一个空白行结束
第二部分是矩阵，矩阵以空格切分，每个项目都是字符，换行则代表记录下一列
输入保证不会出现同一个单词出现在一个以上不同位置的情况
输出格式：
按输入时单词排列的顺序输出序列打印找到的序列起始列号和行号，如果没找到，打印 n，一行一个数据
输入示例：
LESS输出示例：
AMD
AMDM
NCID
ID
SNCI
L E S S A
S J E S M
S N C I D
O N S C M
S K W D J
0 0
0 4
0 4
2 1
2 3
n