Pagini recente » Cod sursa (job #945497) | Cod sursa (job #1703763) | Cod sursa (job #1067032) | lacuricodurimedie | Cod sursa (job #2434200)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int pref[2000005]; char a[2000005], b[2000005];
int rez[2000005], rez1;
void prefix()
{
int n = strlen(b);
int m = strlen(a);
int len = 0;
pref[0] = 0;
int i = 1;
while(i < m)
if(a[i] == a[len])
{
len++;
pref[i] = len;
i++;
}
else
{
if( len > 0)
len = pref[len-1];
else
pref[i] = 0, i++;
}
/*for( j = 0 ; j < m ; j++)
cout << pref[j] << ' ';
cout << '\n';*/
}
void kmp()
{
prefix();
int n = strlen(b);
int m = strlen(a);
int i = 0, j = 0;
while( i < n)
{
if(b[i] == a[j])
i++, j++;
if(j == m)
rez[++rez1] = i - j , j = pref[j - 1];
else if (i < n && b[i] != a[j])
{
if(j > 0)
j = pref[j - 1];
else
i++;
}
}
(rez1 > 1000) ? rez1 = 1000 : rez1 = rez1;
cout << rez1 << '\n';
for(int i = 1 ; i <= rez1 ; i++)
cout << rez[i] << ' ';
}
int main()
{
cin >> a;
cin >> b;
kmp();
return 0;
}