Cod sursa(job #2174523)
Utilizator | Data | 16 martie 2018 12:25:22 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.3 kb |
#include <bits/stdc++.h>
using namespace std;
int supre[2000005], 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<=1000 ; i++ )
{
g<<rsp[i]<<" ";
}
return 0;
}