Pagini recente » Cod sursa (job #2039297) | Cod sursa (job #2375300) | Cod sursa (job #3173627) | Cod sursa (job #2173024) | Cod sursa (job #1022417)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int *pi, *match;
string word, text;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void solve(){
match = new int[text.size()];
pi = new int[word.size()];
pi[0] = -1;
int q = pi[0], 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]){
match[i] = ++q;
if (q != 0)
pi[q] = pi[q-1] + 1;
} else {
match[i] = q;
}
}
}
void print(){
int length = word.size() - 1;
int count = 0;
for (int i = 0; i < text.size(); i++){
if (match[i] == length)
count++;
}
g << count << '\n';
for (int i = 0; i < text.size(); i++){
cout << match[i] << " ";
if (match[i] == length)
g << i - match[i] << " ";
}
}
void read(){
f >> word;
f >> text;
}
int main() {
read();
solve();
print();
delete [] pi;
delete [] match;
return 0;
}