Pagini recente » Cod sursa (job #2321470) | Cod sursa (job #492983) | Cod sursa (job #1232464) | Borderou de evaluare (job #1567408) | Cod sursa (job #2434197)
#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 i = 0;
pref[0] = 0;
int j = 1;
while(j < m)
if(a[i] == a[j])
{
pref[j]++;
i++;
j++;
}
else
{
if( i > 0)
i = pref[i-1];
else
pref[j] = 0, j++;
}
/*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++;
}
}
cout << rez1 << '\n';
for(int i = 1 ; i <= rez1 ; i++)
cout << rez[i] << ' ';
}
int main()
{
cin >> a;
cin >> b;
kmp();
return 0;
}