Pagini recente » Cod sursa (job #2139630) | Cod sursa (job #963377) | Cod sursa (job #1300860) | Cod sursa (job #2613063) | Cod sursa (job #2174501)
#include <bits/stdc++.h>
using namespace std;
int supre[200005], rsp[2000005], cnt;
string pat, s;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
void make_pat()
{
int l = pat.size();
int i = 1 , j = 0;
while ( i < l )
{
if ( pat[j] == pat[i] )
{
supre[i] = j+1;
i++;
j++;
}
else
{
if ( j!=0 )
{
j = supre[ j-1 ];
}
else
{
i++;
}
}
}
}
void kmp()
{
int lpat = pat.size();
int ls = s.size();
int i = 0 , j = 0;
while ( i < ls )
{
if ( s[i] == pat[j] )
{
i++;
j++;
}
else
{
if ( j!=0 )
{
j = supre[j-1];
}
else
{
i++;
}
}
if ( j == lpat )
{
rsp[++cnt] = i-j;
}
}
}
int main ()
{
f>>pat>>s;
make_pat();
kmp();
g<<cnt<<'\n';
for ( int i = 1 ; i <= cnt ; i++ )
{
g<<rsp[i]<<" ";
}
}