Pagini recente » Cod sursa (job #463532) | Cod sursa (job #457750) | Cod sursa (job #752583) | Cod sursa (job #303639) | Cod sursa (job #3147828)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int STRLEN_MAX = 2e5;
const char SEPARATOR = '&';
const int POS_MAX = 1e3;
char str[2 * STRLEN_MAX + 2];
char aux[STRLEN_MAX];
int z[2 * STRLEN_MAX + 1];
int pos[POS_MAX];
int ZRead(){
fin >> str;
int pattern_length = 0;
while(str[pattern_length])
++pattern_length;
str[pattern_length] = SEPARATOR;
fin >> aux;
int i = 0;
while(aux[i]){
str[i + pattern_length + 1] = aux[i];
++i;
}
str[i + pattern_length + 1] = '\0';
return pattern_length;
}
void ComputeZFunction(){
int left = 0, right = 0, i = 1;
z[0] = 0;
while(str[i]){
if(i <= right)
z[i] = min(z[i - left], right - i + 1);
else
z[i] = 0;
while(str[z[i]] == str[i + z[i]])
++z[i];
if(i + z[i] > right){
right = i + z[i];
left = i;
}
++i;
}
}
int ZAlgorithm(){
int pattern_len = ZRead();
ComputeZFunction();
int i = 0, matches = 0;
while(str[i]){
if(z[i] == pattern_len){
if(matches < POS_MAX)
pos[matches] = i - pattern_len - 1;
++matches;
}
++i;
}
return matches;
}
int main(){
int matches = ZAlgorithm();
fout << matches << '\n';
if(matches > POS_MAX)
matches = POS_MAX;
for(int i = 0; i < matches; ++i)
fout << pos[i] << ' ';
fout.put('\n');
fin.close();
fout.close();
return 0;
}