Pagini recente » Cod sursa (job #2646641) | Cod sursa (job #2843449) | Cod sursa (job #475196) | Cod sursa (job #1938001) | Cod sursa (job #1524120)
#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()
{
int k = -1;
p[0] = k;
int i = 0;
while(i < l)
{
while(k >= 0 && pat[i] != pat[k]) k = p[k];
k++;
i++;
p[i] = 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();
p.resize(l+1, 0);
prefix();
getMatches();
cout << matches.size() << '\n';
for(int i = 0; i < matches.size(); i++)
{
if(i > 1000)
break;
cout << matches[i];
}
}