Pagini recente » Cod sursa (job #2606584) | Cod sursa (job #1772198) | Cod sursa (job #3255706) | Cod sursa (job #1797832) | Cod sursa (job #954980)
Cod sursa(job #954980)
#include <string>
#include <fstream>
#include <list>
#include <iostream>
using namespace std;
void create_automaton(const string &pattern, int *pi){
int i, k=0;
}
list<int> find_matches(const string &pattern, const string &text, int *pi){
list<int> result;
int i, k=0;
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()], i, k;
create_automaton(pattern, pi);
//CREATE AUTOMATON
pi[0] = 0;
k = 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;
}
k=0;
//FIND MATCHES
list<int> result;
for(i=0; i<text.size(); i++){
while(k>0 && text[i]!=pattern[k])
k=pi[k-1];
if(text[i] == pattern[k])
k++;
if(k==pattern.size()){
result.push_back(i-pattern.size()+1);
k=pi[k-1];
}
}
out<<result.size()<<endl;
for(int i: result)
out<<i<<" ";
in.close();
out.close();
return 0;
}