Pagini recente » Cod sursa (job #1933665) | Cod sursa (job #2342384) | Cod sursa (job #1042178) | Cod sursa (job #2847280) | Cod sursa (job #1652208)
#include <fstream>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern , text;
int pre[2000005] , pos[1005] , n , m , num;
int main()
{
f >> pattern >> text;
n = pattern.size();
m = text.size();
for(int i = n; i; --i) pattern[i] = pattern[i - 1]; pattern[0] = ' '; // indexez de la 1
for(int i = m; i; --i) text[i] = text[i - 1]; text[0] = ' ';
int k = 0;
for(int i = 2; i <= n; ++i)
{
while(k && pattern[k + 1] != pattern[i])
k = pre[k];
if(pattern[k + 1] == pattern[i])
++k;
pre[i] = k;
}
k = 0;
for(int i = 1; i <= m; ++i)
{
while(k && pattern[k + 1] != text[i])
k = pre[k];
if(pattern[k + 1] == text[i])
k++;
if(k == n)
{
num++;
k = pre[n];
if(num <= 1000)
pos[num] = i - n;
}
}
g << num << "\n";
for(int i = 1; i <= min(num , 1000); ++i)
g << pos[i] << " ";
return 0;
}