Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:一样的算法, 2406(141ms), 1961(tle), 就多个输出, 这么费时么, 我的算法应该是O(n)呀!求大神给看看!

Posted by 455952523 at 2011-05-19 14:13:46 on Problem 1961
In Reply To:一样的算法, 2406(141ms), 1961(tle), 就多个输出, 这么费时么, 我的算法应该是O(n)呀!求大神给看看! Posted by:sicojuy at 2011-04-24 12:37:40
```> #include <cstdio>
> #include <cstring>
> #define N 1000001
>
> char str[N], substr[N];
>
> int main()
> {
>     char *p, *strend;
>     int len, ppos;
>     int period, count;
> 	int test = 0;
>     while(scanf("%d", &len), len != 0)
>     {
> 		scanf("%s", str);
> 		printf("Test case #%d\n", ++test);
> 		ppos = 0;
> 		p = str;
> 		strend = str + len;
> 		while(p < strend)
> 		{
> 		    period = p - str + 1;
> 		    while(ppos < period)
>             {
>                 substr[ppos] = str[ppos];
>                 ++ppos;
>                 p = str + period;
>             }
>             substr[ppos] = '\0';
>             count = 1;
>             while(strncmp(p, substr, period) == 0)
>             {
>                 ++count;
>                 p += period;
>                 printf("%d %d\n", int(p - str), count);
>             }
> 		}
>         printf("\n");
>     }
>     return 0;
> }
```

Followed by: