Pagini recente » Cod sursa (job #1322302) | Cod sursa (job #2414926) | Cod sursa (job #2380448) | Cod sursa (job #2196491) | Cod sursa (job #3147353)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int STRLEN_MAX = 2e6;
const int POS_MAX = 1e3;
char pattern[STRLEN_MAX + 1], str[STRLEN_MAX + 1];
int lps[STRLEN_MAX], pos[POS_MAX], n = 0;
void PrecomputeLPS(const char* pattern){
int i = 1, pefixLen;
lps[0] = 0;
while(pattern[i]){
pefixLen = lps[i - 1];
while(pefixLen && pattern[pefixLen] != pattern[i])
pefixLen = lps[pefixLen - 1];
if(pattern[pefixLen] == pattern[i])
lps[i] = pefixLen + 1;
else
lps[i] = 0;
++i;
}
}
void KMP(const char* str, const char* pattern){
PrecomputeLPS(pattern);
int i = 0, j = 0;
while(str[i]){
if(pattern[j] == str[i]){
++i, ++j;
if(!pattern[j]){
if(n < POS_MAX)
pos[n] = i - j;
n++;
j = lps[j - 1];
}
}else{
if(j > 0)
j = lps[j - 1];
else
++i;
}
}
}
int main(){
fin >> pattern >> str;
KMP(str, pattern);
fout << n << '\n';
if(n > POS_MAX)
n = POS_MAX;
for(int i = 0; i < n; ++i)
fout << pos[i] << ' ';
fout.put('\n');
fin.close();
fout.close();
return 0;
}