Pagini recente » Istoria paginii utilizator/sliviu | Cod sursa (job #2893206) | Cod sursa (job #3181289) | Cod sursa (job #2220766) | Cod sursa (job #1674751)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2000003;
int n, m, pref[N], rez[N], poz;
char a[N], b[N], c;
void calculprefixe()
{
int k = 0, i;
pref[1] = 0;
for ( i = 2; i <= m; i++ )
{
while( k > 0 && a[k+1] != a[i] )
k = pref[k];
if (a[k+1] == a[i]) //if ( k != 0 )
k++;
pref[i] = k;
}
}
void kmp()
{
int k = 0, i;
for ( i = 1; i <= n; i++ )
{
while( k > 0 && a[k+1] != b[i] )
k = pref[k];
if ( a[k+1] == b[i] ) //if ( k != 0 )
k++;
if ( k == m ) /// am potrivire la poz i-m
{
poz++;
rez[poz] = i-m;
}
}
}
int main()
{
in.get(c);
while( c != '\n' && c != NULL )
{
m++;
a[m] = c;
in.get(c);
}
in.get(c);
while( c != '\n' && c != NULL )
{
n++;
b[n] = c;
in.get(c);
}
calculprefixe();
kmp();
out << poz<<'\n';
for ( int i = 1; i <= poz; i++ )
out << rez[i]<<' ';
return 0;
}