Pagini recente » Cod sursa (job #3219547) | Cod sursa (job #494434) | Cod sursa (job #995694) | Cod sursa (job #713630) | Cod sursa (job #2765273)
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector<int> results;
int count = 0;
void kmp(string text,string pattern)
{
int size = pattern.size();
int table[size];
table[0] = 0;
int k = 0;
for(int i = 1; i < size; i++) {
while (k > 0 && pattern[k] != pattern[i] )
{
k = table[k-1];
}
if (pattern[k] == pattern[i])
{
k = k + 1;
}
table[i] = k;
}
// for (int i = 0; i < size; i++)
// cout << table[i] << " ";
// cout << "\n";
int matched_pos=0;
for(int current=0; current< text.length(); current++) {
while (matched_pos > 0 && pattern[matched_pos] != text[current] )
matched_pos = table[matched_pos-1];
if(pattern[matched_pos] == text[current])
matched_pos = matched_pos + 1;
if( matched_pos == (pattern.length())) {
if (results.size() < 1000)
results.push_back(current - (pattern.length() - 1));
count++;
matched_pos = table[matched_pos-1];
}
}
}
int main()
{
string text, pattern;
f >> pattern;
f >> text;
kmp(text,pattern);
g << count << "\n";
for (int i = 0; i < results.size(); i++)
g << results[i] << " ";
return 0;
}