Pagini recente » Cod sursa (job #1445288) | Cod sursa (job #1926356) | Cod sursa (job #3171695) | Cod sursa (job #1090689) | Cod sursa (job #1022430)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int *pi, rez[1000], count;
string word, text;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void compute_pi_function(string word) {
int length = word.size();
pi = new int[length];
pi[0] = -1;
for (int i = 1; i < length; i++){
int q = pi[i-1];
while (q != -1 && word[i] != word[q+1])
q = pi[q];
if (word[i] == word[q+1])
++q;
pi[i] = q;
}
}
void solve(){
int q = -1, length = word.size();
for (int i = 0; i < text.size(); i++){
while (q != -1 && text[i] != word[q+1])
q = pi[q];
if (text[i] == word[q+1])
++q;
if (q == length - 1){
if (count <= 1000)
rez[count] = i - q;
count++;
}
}
}
void print(){
g << count << "\n";
int min = count > 1000 ? 1000 : count;
for(int i = 0; i < min; i++)
g << rez[i] << " ";
}
void read(){
f >> word;
f >> text;
}
int main() {
read();
compute_pi_function(word);
solve();
print();
delete [] pi;
return 0;
}