Pagini recente » Cod sursa (job #2243534) | Cod sursa (job #3174111) | Cod sursa (job #840320) | Cod sursa (job #655333) | Cod sursa (job #2339630)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000010];
char t[2000010];
int sol[1002];
int p[2000010];
int n, m, L, aparitii = 0, i;
int main()
{ fin >> s + 1;
fin >> t + 1;
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";
if (aparitii > 1000)
aparitii = 1000;
for (i=1;i<=aparitii;i++)
fout<<sol[i]<<" ";
return 0;
}