Find a Two-Dimensional Word
National Olympiad — National round (2019 season)
Submission name: thracians.cpp
Problem summary
Count occurrences of a letter matrix R×C inside a streamed letter matrix N×M, including overlapping occurrences, using at most 4 MB memory.
Input
R C and the pattern rows; N M and the text rows.
Output
The occurrence count.
Constraints
1 ≤ R,C ≤ 100; 1 ≤ N,M ≤ 5000; memory limit 4 MB.
Worked example
An independently prepared example for this explanation.
Input
2 2 aa ab 3 3 aaa aab aba
Output
2
Solution analysis
- Give every distinct pattern row a unique identifier. Build an Aho–Corasick automaton for these equal-length rows. Scanning one text row identifies at each ending column which pattern row, if any, ends there. Equal pattern rows deliberately share an identifier.
- The pattern now becomes a one-dimensional sequence of R row identifiers. For each text column keep a KMP state matching that sequence vertically. Feed the row identifier ending at this column into that state; whenever it reaches R, a full matrix occurrence ends here. Follow the prefix link afterward to retain overlapping matches.
- For pattern aa / ab, row aaa gives identifier aa at ending columns 2 and 3. On the next row aab, column 3 gives identifier ab and completes one match. The third row aba completes another at column 2. Only one row and one KMP state per column are stored.
Why it works
Equal-length row patterns let the automaton label a text suffix uniquely exactly when its C letters equal a pattern row. A matrix occurrence is therefore equivalent to R consecutive row labels at one ending column matching the pattern’s row-label sequence. KMP detects precisely these vertical matches, and its prefix fallback preserves all overlaps. Each reported match corresponds to one unique top-left position.
Watch out. Do not store the full text or a row-by-column match matrix. Merge identical pattern rows. Retain overlaps both horizontally and vertically.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<queue>
#include<string>
#include<vector>
// Algorithm: Give every distinct pattern row a unique identifier.
using namespace std;
struct Node{
array<int,26>next{};
int failure=0;
int label=0;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int r,c;
cin>>r>>c;
vector<Node>automaton;
automaton.reserve(r*c+1);
automaton.emplace_back();
vector<int>pattern(r);
int labels=0;
for(int i=0;i<r;i++){
string row;
cin>>row;
int state=0;
for(char letter:row){
int symbol=letter-'a';
if(!automaton[state].next[symbol]){
automaton[state].next[symbol]=static_cast<int>(automaton.size());
automaton.emplace_back();
}
state=automaton[state].next[symbol];
}
if(!automaton[state].label){
automaton[state].label=++labels;
}
pattern[i]=automaton[state].label;
}
queue<int>pending;
for(int symbol=0;symbol<26;symbol++){
if(automaton[0].next[symbol]){
pending.push(automaton[0].next[symbol]);
}
}
while(!pending.empty()){
int u=pending.front();
pending.pop();
for(int symbol=0;symbol<26;symbol++){
int v=automaton[u].next[symbol];
if(v){
automaton[v].failure=automaton[automaton[u].failure].next[symbol];
pending.push(v);
}
else{
automaton[u].next[symbol]=automaton[automaton[u].failure].next[symbol];
}
}
}
vector<int>prefix(r);
for(int i=1;i<r;i++){
int j=prefix[i-1];
while(j&&pattern[i]!=pattern[j]){
j=prefix[j-1];
}
if(pattern[i]==pattern[j]){
j++;
}
prefix[i]=j;
}
int n,m;
cin>>n>>m;
vector<int>matched(m);
long long answer=0;
for(int i=0;i<n;i++){
string row;
cin>>row;
int state=0;
for(int column=0;column<m;column++){
state=automaton[state].next[row[column]-'a'];
int label=automaton[state].label;
int j=matched[column];
while(j&&pattern[j]!=label){
j=prefix[j-1];
}
if(pattern[j]==label){
j++;
}
if(j==r){
answer++;
j=prefix[j-1];
}
matched[column]=j;
}
}
cout<<answer<<'\n';
}