Pagini recente » Cod sursa (job #3209929) | Cod sursa (job #24580) | Cod sursa (job #991185) | Cod sursa (job #1677935) | Cod sursa (job #2299818)
#include <bits/stdc++.h>
#define Nmax 2*2000000+100
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char pat[Nmax], str[Nmax];
int phi[Nmax], m, sol, x;
vector <int> Sol;
inline void build_phi()
{
int rez=0;
phi[0]=0;
strcat(pat, "#");
strcat(pat, str);
x = strlen(pat);
for(int i = 1 ; i < x ; i++ )
{
while(rez > 0 && pat[i] != pat[rez])
{
rez = phi[rez-1];
}
if(pat[i] == pat[rez])
{
rez++;
}
phi[i] = rez;
}
}
inline void solve()
{
build_phi();
for(int i = m+1 ; i < x ; i ++ )
{
if(phi[i] == m)
{
sol++;
Sol.push_back(i);
}
}
g<<sol<<'\n';
for(int i = 0 ; i <= 1000 && i<Sol.size() ; i++)
{
g<<Sol[i] - 2*m << " ";
}
}
int main()
{
f.getline(pat , 2000000);
f.getline(str , 2000000);
m = strlen(pat);
solve();
return 0;
}