Pagini recente » Cod sursa (job #472571) | Cod sursa (job #2085544) | Cod sursa (job #1137729) | Cod sursa (job #1892992) | Cod sursa (job #2168082)
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int dp[2000005], rsp[2000005], cnt;
string pat, s;
void make_pat ()
{
int i = 1, j = 0;
int l = pat.size();
while ( i < l )
{
if ( pat[i] == pat[j] )
{
dp[i] = j + 1;
i++;
j++;
}
else
{
if ( j!= 0 )
{
j = dp[ j-1 ];
}
else
{
i++;
}
}
}
}
void kmp ()
{
int i = 0 , j = 0;
int ls = s.size();
int lpat = pat.size();
while ( i < ls )
{
if ( s[i] == pat[j] )
{
i++;
j++;
}
else
{
if ( j!=0 )
{
j = dp[j-1];
}
else
{
i++;
}
}
if ( j == lpat )
{
rsp[++cnt] = i - lpat;
}
}
}
int main ()
{
f>>pat>>s;
make_pat();
kmp();
g<<cnt<<'\n';
for ( int i = 1; i <= cnt && i <= 1000 ; i++ )
{
g<<rsp[i]<<" ";
}
return 0;
}