Pagini recente » Cod sursa (job #384409) | Cod sursa (job #1894814) | Istoria paginii runda/oni_2009_1_10/clasament | Cod sursa (job #1090132) | Cod sursa (job #955049)
Cod sursa(job #955049)
#include <string>
#include <fstream>
#include <list>
#include <iostream>
using namespace std;
void create_automaton(const string &pattern, int *pi){
int i, k=0;
pi[0] = 0;
for(i=1; i<pattern.size(); i++){
while(k>0 && pattern[i]!=pattern[k])
k=pi[k];
if(pattern[i]==pattern[k])
k++;
pi[i] = k;
}
}
list<int> find_matches(const string &pattern, const string &text, int *pi){
list<int> result;
int i, k=0;
for(i=0; i<text.size(); i++){
while(k>0 && text[i]!=pattern[k])
k=pi[k];
if(text[i] == pattern[k])
k++;
if(k==pattern.size()){
result.push_back(i-pattern.size()+1);
k=pi[k-1];
}
if(result.size()==1000)
return result;
}
return result;
}
int main(){
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string pattern , text;
getline(in, pattern);
getline(in, text);
int pi[pattern.size()];
create_automaton(pattern, pi);
list<int> result = find_matches(pattern, text, pi);
out<<result.size()<<endl;
for(int i: result)
out<<i<<" ";
in.close();
out.close();
return 0;
}