Pagini recente » Arbori de intervale si aplicatii in geometria computationala | Cod sursa (job #3281517) | Cod sursa (job #3224249) | Cod sursa (job #3285584) | Cod sursa (job #1524155)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string pat, s;
vector <int> p;
int l, n;
void prefix()
{
p.push_back(-1);
int k = -1;
int i = 0;
while(i < l)
{
while(k >= 0 && pat[i] != pat[k]) k = p[k];
k++;
i++;
p.push_back(k);
}
}
vector <int> matches;
void getMatches()
{
int j = 0;
int i = 0;
while(i < n)
{
while( j >= 0 && s[i] != pat[j])
{
j = p[j];
}
j++;
i++;
if( j == l)
{
matches.push_back(i-j);
j = p[j];
}
}
}
int main()
{
cin >> pat;
cin >> s;
l = pat.length();
n = s.length();
prefix();
getMatches();
cout << matches.size() << '\n';
for(int i = 0; i < matches.size() && i < 1000 ; i++)
{
cout << matches[i] << ' ';
}
}