Pagini recente » Cod sursa (job #1410212) | Cod sursa (job #702701) | Cod sursa (job #519590) | Cod sursa (job #38923) | Cod sursa (job #2339606)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000001],t[2000001];
int main()
{ fin >> s + 1;
fin >> t + 1;
int aparitii = 0,n, m,L,sol[2000001],i,p[2000001];
n = strlen(s + 1);
m = strlen(t + 1);
p[1] = 0;
L = 0;
for(i = 2; i <= n; ++i)
{
//calculez p[i];
while(L != 0 && s[i] != s[L + 1])
L = p[L];
if(s[i] == s[L + 1])
L++;
p[i] = L;
}
L = 0;
for(i = 1; i <= m; ++i)
{
///testam potrivire a lui s in t care se termina la pozitia i
// semnificatia lui L la pasul i = lungimea maxima a unui sufix din t terminat la pozitia i care totodata este prefix de lungime L in s
while(L != 0 && t[i] != s[L + 1])
L = p[L];
if(t[i] == s[L + 1])
L++;
if(L == n) //potrivire;
//fout<<i - n + 1;
aparitii++;
if(aparitii <= 1000)
sol[aparitii] = i - n;
L = p[L]; // urmatoarea potrivire se poate suprapune cu cea curenta
//o cautam extinzand prefixul cel mai lung prefix al intregului sir s;
}
fout<<aparitii<<'\n';
int lg = aparitii % 1001;
for(i = 1; i <= lg; ++i)
{
fout<<sol[i]<<' ';
}
return 0;
}