Pagini recente » Cod sursa (job #1258735) | Cod sursa (job #2224765) | Cod sursa (job #471395) | Cod sursa (job #1535547) | Cod sursa (job #1922483)
#include <fstream>
using namespace std;
string pat, txt;
int lpat, ltxt, dp[2000005], i, nr, sol[2000005];
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
void din ()
{
int i=0, j = 1;
while ( j < lpat )
{
if ( pat [i] == pat [j] )
{
dp[j] = i + 1;
i++;
j++;
}
else
{
if ( i != 0 )
{
i = dp [i-1];
}
else
{
j++;
}
}
}
}
void rez()
{
int i = 0, j = 0;
while ( j < ltxt )
{
if ( pat [ i ] == txt [ j ] )
{
i++;
j++;
}
else
{
if ( i != 0 )
{
i = dp [ i - 1 ];
}
else
{
j++;
}
}
if ( i == lpat )
{
nr++;
sol [ nr ] = j - lpat ;
}
}
}
int main ()
{
f>>pat>>txt;
lpat = pat.size();
ltxt = txt.size();
din();
rez();
g<<nr<<'\n';
for ( i = 1 ; i <= nr && i <= 1000 ; i++ )
{
g<<sol[i]<<" ";
}
return 0;
}